Problem Statement

$N$ cells $1,2,...,N$ are arranged adjacently in a line.
For $1 \leq i < N$, cells $i$ and $i+1$ are adjacent.
The player can move to an adjacent cell by paying a cost of $1$.
Some cells may have teleporters installed.
If a teleporter with cost $c$ is installed at cell $x$, the player can move to cell $x$ by paying a cost of $c$, regardless of their current position.

Initially, there are no teleporters.
You are given $Q$ queries; process them in order.

• Query 1 : Output the minimum cost to move from cell $1$ to cell $x$.
• Query 2 : Newly install a teleporter with cost $c$ at cell $x$.

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• At least one Query 1 is given
• For Query 1, $1 \leq x \leq N$
• For Query 2, $1 \leq x \leq N$
• For Query 2, $1 \leq c \leq 10^9$

Input

The input is given from standard input in the following format.

$N$ $Q$
$Query_1$
$Query_2$
$\vdots$
$Query_Q$

$Query_i$ is given in the following format.

For Query 1:

$1$ $x$

For Query 2:

$2$ $x$ $c$

Output

Output the answers to Query 1 in the order given, separated by newlines.

10 5
1 10
2 5 1
1 10
2 8 10000
1 10

9
6
6