Soit une séquence $P = \{0, 1, 2, \cdots, N-1\}$ de $N$ éléments.

Pour la séquence $P$, l'arbre $T_P$ est défini comme suit :

• Il a $N$ sommets au total.
• Le sommet $1$ est la racine, et pour $2 \le i \le N$, le parent du sommet $i$ est le sommet $\max(P_i, 1)$.

Écrivez un programme qui effectue les requêtes suivantes :

• $1 \ x \ a$ : soustraire $a$ de chacun des éléments $P_x, P_{x+1}, \cdots, P_N$.
• $2 \ x \ y$ : afficher le numéro du plus petit ancêtre commun des deux sommets $x$ et $y$ dans l'arbre $T_P$ défini par la séquence $P$ actuelle.

Entrée

La première ligne contient deux entiers $N$ et $Q$ séparés par une espace. ($1 \le N, Q \le 100\,000$)

Les $Q$ lignes suivantes, la $i+1$-ième ligne, contiennent trois entiers séparés par une espace représentant la $i$-ième requête. ($1 \le x, y, a \le N$)

Sortie

Pour chaque requête de type 2, affichez la réponse sur une ligne distincte.

Il est garanti qu'au moins une requête de type 2 est donnée.

Exemples

Entrée 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

Sortie 1

1
1
2
5
1

Entrée 2

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

Sortie 2

9
1
1