$N$個の要素からなる数列 $P=\{0, 1, 2, \cdots, N-1\}$ がある。

数列 $P$ に対して、木 $T_P$ は次のように定義される。

• 合計 $N$ 個の頂点を持つ。
• $1$ 番の頂点は根であり、$2 \le i \le N$ に対して $i$ 番の頂点の親は $\max(P_i, 1)$ 番の頂点である。

以下のクエリを実行するプログラムを作成せよ。

• $1 \ x \ a$: $P_x, P_{x+1}, \cdots, P_N$ からそれぞれ $a$ を引く。
• $2 \ x \ y$: 現在の数列 $P$ に対して定義された木 $T_P$ において、二つの頂点 $x$ と $y$ の最小共通祖先の番号を出力する。

入力

最初の行に二つの整数 $N$, $Q$ が空白区切りで与えられる。($1 \le N, Q \le 100\,000$)

二行目以降 $Q$ 行にわたって、$i+1$ 行目に $i$ 番目のクエリを表す $3$ つの整数が空白区切りで与えられる。($1 \le x, y, a \le N$)

出力

2 番のクエリが与えられるたびに、答えを一行に一つずつ出力する。

2 番のクエリは一つ以上与えられることが保証される。

入出力例

入力 1

6 9
1 6 1
1 2 1
2 6 1
1 5 1
2 1 3
2 4 6
1 5 2
2 5 5
2 6 2

出力 1

1
1
2
5
1

入力 2

13 5
1 12 2
2 11 12
1 2 2
2 2 9
2 2 6

出力 2

9
1
1