Il y a une forêt composée de $N$ sommets. Les sommets sont numérotés de $1$ à $N$. Initialement, la forêt ne contient aucune arête.

Écrivez un programme qui exécute les requêtes suivantes.

• 1 u v : Ajoute une arête reliant les deux sommets $u$ et $v$ dans la forêt. Avant l'appel de cette requête, il est garanti qu'il n'existe aucun chemin entre $u$ et $v$ dans la forêt.
• 2 u k : Soit $dist(u, v)$ la longueur du plus court chemin entre deux sommets $u$ et $v$. Si les deux sommets ne sont pas connectés, cette valeur est $\infty$. Retournez le nombre de sommets $v$ tels que $dist(u, v) = k$.

Entrée

La première ligne contient deux entiers $N, Q$. ($1 \le N \le 100\,000, 1 \le Q \le 200\,000$)

Les $Q$ lignes suivantes contiennent trois entiers $t_i, a_i, b_i$ représentant les informations des requêtes. ($1 \le t_i \le 2, 0 \le a_i, b_i < n$)

Considérons une variable supplémentaire $last$. Cette variable vaut initialement $0$.

• Lorsque $t_i = 1$, les arguments $u_i, v_i$ sont définis comme suit : $u_i = ((a_i + last) \bmod n) + 1$, $v_i = ((b_i + last) \bmod n) + 1$.
• Lorsque $t_i = 2$, les arguments $u_i, k_i$ sont définis comme suit : $u_i = ((a_i + last) \bmod n) + 1$, $k_i = ((b_i + last) \bmod n)$. Après avoir calculé la réponse à cette requête, $last$ est mis à jour avec cette réponse.

Sortie

Affichez les réponses aux requêtes de type $t_i = 2$, une par ligne.

Exemples

Entrée 1

7 9
1 0 6
1 4 3
1 0 5
1 1 2
1 3 1
1 4 5
2 2 3
2 2 1
2 0 0

Sortie 1

1
2
1