Hay una secuencia $P = \{0, 1, 2, \cdots, N-1\}$ de $N$ elementos.

Para la secuencia $P$, el árbol $T_P$ se define de la siguiente manera:

• Tiene un total de $N$ vértices.
• El vértice $1$ es la raíz, y para $2 \le i \le N$, el padre del vértice $i$ es el vértice $\max(P_i, 1)$.

Escribe un programa que realice las siguientes consultas:

• $1 \ x \ a$: resta $a$ de cada elemento $P_x, P_{x+1}, \cdots, P_N$.
• $2 \ x \ y$: imprime el número del ancestro común más cercano de los dos vértices $x$ y $y$ en el árbol $T_P$ definido por la secuencia actual $P$.

Entrada

En la primera línea se dan dos enteros $N$, $Q$ separados por un espacio. ($1 \le N, Q \le 100\,000$)

A partir de la segunda línea, en cada una de las $Q$ líneas siguientes, se dan tres enteros separados por espacios que representan la $i$-ésima consulta en la línea $i+1$. ($1 \le x, y, a \le N$)

Salida

Siempre que se dé una consulta de tipo 2, imprime la respuesta en una línea. Está garantizado que se dará al menos una consulta de tipo 2.

Ejemplos

Entrada 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

Salida 1

1
1
2
5
1

Entrada 2

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

Salida 2

9
1
1