Имеется последовательность $P = \{0, 1, 2, \ldots, N-1\}$ из $N$ элементов.

Для последовательности $P$ дерево $T_P$ определяется следующим образом:

• Оно содержит всего $N$ вершин.
• Вершина $1$ является корнем, а для $2 \le i \le N$ родителем вершины $i$ является вершина $\max(P_i, 1)$.

Напишите программу, которая выполняет следующие запросы:

• $1 \; x \; a$: вычесть $a$ из элементов $P_x, P_{x+1}, \ldots, P_N$.
• $2 \; x \; y$: вывести номер наименьшего общего предка вершин $x$ и $y$ в дереве $T_P$, определённом по текущей последовательности $P$.

Входные данные

В первой строке даны два целых числа $N$, $Q$, разделённые пробелом. ($1 \le N, Q \le 100\,000$)

В следующих $Q$ строках (со второй по $(Q+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