問題文

$N$個のマス $1,2,...,N$ が直線上に隣接して並んでいます。
$1 \leq i < N$ について、マス $i$ と $i+1$ は隣接しています。
プレイヤーは、コストを $1$ 支払うことで隣接するマスに移動することができます。
マスにはテレポーターが設置されている場合があります。
マス $x$ にコスト $c$ のテレポーターが設置されている場合、現在位置に関わらず、コスト $c$ 支払うことでマス $x$ へ移動することができます。

最初、テレポーターは存在しません。
$Q$ 個のクエリが与えられるので、順に処理してください。

• クエリ1 : マス $1$ からマス $x$ まで移動するためのコストの最小値を出力する。
• クエリ2 : マス $x$ に、新しくコスト $c$ のテレポーターを設置する。

制約

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• クエリ1は一つ以上与えられる
• クエリ1について、 $1 \leq x \leq N$
• クエリ2について、 $1 \leq x \leq N$
• クエリ2について、 $1 \leq c \leq 10^9$

入力

入力は以下の形式で標準入力から与えられる。

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

$Query_i$は以下の形式で与えられる。

クエリ1の場合、

$1$ $x$

クエリ2の場合、

$2$ $x$ $c$

出力

クエリ1の答えを、与えられた順に改行区切りで出力せよ。

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

9
6
6