There is a sequence $P$ of $N$ elements: $P = \{0, 1, 2, \dots, N-1\}$.

For the sequence $P$, the tree $T_P$ is defined as follows:

• It has a total of $N$ vertices.
• Vertex $1$ is the root. For $2 \le i \le N$, the parent of vertex $i$ is vertex $\max(P_i, 1)$.

Write a program that processes the following queries:

• $1 \ x \ a$: Subtract $a$ from each of $P_x, P_{x+1}, \dots, P_N$.
• $2 \ x \ y$: Output the number of the lowest common ancestor of vertices $x$ and $y$ in the tree $T_P$ defined with the current sequence $P$.

Input

The first line contains two integers $N$, $Q$ separated by a space. ($1 \le N, Q \le 100\,000$)

From the second line onward, $Q$ lines are given. The $i+1$-th line contains three integers representing the $i$-th query, separated by spaces. ($1 \le x, y, a \le N$)

Output

Whenever a type-2 query is given, output the answer on its own line.

It is guaranteed that at least one type-2 query is given.

Examples

Input 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

Output 1

1
1
2
5
1

Input 2

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

Output 2

9
1
1