C : Big Range Query

$N$ 個の数字からなる数列$\{a_i\}$ ($1 \leqq i \leqq N$) と, クエリが$Q$ 個与えられる. ここで, $i$ 番目の数値の初期値は$i$ である. すなわち, 初期状態では$a_i=i$ である. クエリは次の3 つのうちいずれかである :

• 区間$[l,\ r]$ の数値の最小値を求める. すなわち, $l \leqq x \leqq r$ を満たす$x$ について, $\min a_{x}$ を求める.
• 区間$[l,\ r]$ の数値の最大値を求める. すなわち, $l \leqq x \leqq r$ を満たす$x$ について, $\max a_{x}$ を求める.
• 場所$k$ の数値を$x$ に変更する. すなわち, $a_k = x$ とする.

この$Q$ 個のクエリを処理せよ.

入力

1 行目に, 整数値$N$ と$Q$ が空白区切りで与えられる.
2 行目から$1 + i$ 行目 ($1 \leqq i \leqq Q$) に, クエリが書かれている.
$1 + i$ 行目の最初の数値が1 であるとき, 後ろに数字$l,\ r$ がこの順で空白区切りで書かれている. これは, 区間$[l,\ r]$の最小値を求めるクエリを指す.
$1 + i$ 行目の最初の数値が2 であるとき, 後ろに数字$l,\ r$ がこの順で空白区切りで書かれている. これは, 区間$[l,\ r]$の最大値を求めるクエリを指す.
$1 + i$ 行目の最初の数値が3 であるとき, 後ろに数字$k,\ x$ がこの順で空白区切りで書かれている. これは,位置$k$ の数値を$x$ に変更するクエリを指す.

制限

• $1 \leqq N \leqq 10^9$ 数列の長さ
• $1 \leqq Q \leqq 10^5$ クエリの個数
• 数列の添字は1-indexed で与えられる.
• クエリを与える前後で, 数列の各数値は $-10^9 \leqq a_i \leqq 10^9$ を必ず満たす.

出力

1 と2 のタイプのクエリに対して, 条件を満たす数値を出力せよ.

入出力例

入力例 1

5 3
1 1 5
3 3 30
2 2 4

出力例 1

1
30

クエリが与えられる過程で, 数列は次の様に変化する.

入力例 2

10 10
1 2 2
3 2 -2
2 2 2
2 1 10
1 1 8
3 1 10
3 2 1000000000
1 1 2
2 2 2
1 2 5

出力例 2

2
-2
10
-2
10
1000000000
3