有一个包含 $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$ 个查询，以空格分隔。($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