Dany jest ciąg $P = \{0, 1, 2, \ldots, N-1\}$ składający się z $N$ elementów.

Dla ciągu $P$ drzewo $T_P$ definiujemy następująco:

• Ma ono $N$ wierzchołków.
• Wierzchołek $1$ jest korzeniem, a dla każdego $i$ ($2 \le i \le N$) rodzicem wierzchołka $i$ jest wierzchołek $\max(P_i, 1)$.

Napisz program wykonujący następujące zapytania:

• $1 \ x \ a$: odejmij $a$ od każdego z elementów $P_x, P_{x+1}, \ldots, P_N$.
• $2 \ x \ y$: wypisz numer najniższego wspólnego przodka wierzchołków $x$ i $y$ w drzewie $T_P$ zdefiniowanym dla bieżącego ciągu $P$.

Wejście

W pierwszym wierszu podane są dwie liczby całkowite $N$ i $Q$ oddzielone pojedynczą spacją. ($1 \le N, Q \le 100\,000$)

W kolejnych $Q$ wierszach (od drugiego do $Q+1$-ego) podane są trzy liczby całkowite oddzielone spacjami, oznaczające $i$-te zapytanie. ($1 \le x, y, a \le N$)

Wyjście

Dla każdego zapytania typu 2 wypisz w osobnym wierszu odpowiedź.

Zapewnione jest, że co najmniej jedno zapytanie typu 2 występuje.

Przykład

Wejście 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

Wyjście 1

1
1
2
5
1

Wejście 2

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

Wyjście 2

9
1
1