Il y a une forêt composée de $N$ sommets. Les sommets sont numérotés de $1$ à $N$ et il n'y a pas d'arêtes. Chaque sommet $v$ possède un entier $X_v$, initialement $X_v = 1$.

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

• 1 $a$ $b$ $c$ : Connecter les sommets $a$ et $b$ par une arête de poids $c$. L'entrée garantit que le résultat de la requête est une forêt.
• 2 $a$ $b$ : Supprimer l'arête reliant les sommets $a$ et $b$. L'entrée garantit que cette arête existe.
• 3 $a$ : Changer $X_a$ en $1-X_a$. Ensuite, dans l'arbre contenant $a$, calculer la valeur suivante.
  • Soient $v_1, v_2, \dots, v_k$ les sommets de l'arbre. Calculer $\displaystyle \min_{1 \le i \le k}{\left\{ \sum_{1 \le j \le k}{dist(v_i, v_j) \times X_{v_j}} \right\}}$ et l'afficher. $dist(v_i, v_j)$ est la somme des poids de toutes les arêtes sur le chemin de $v_i$ à $v_j$.

Entrée

La première ligne contient le nombre de sommets $N$ et le nombre de requêtes $Q$. Les $Q$ lignes suivantes contiennent chacune une requête.

Les numéros de sommets donnés dans les requêtes ($a$, $b$ pour les requêtes de type 1 et 2, $a$ pour la requête de type 3) sont chiffrés et doivent être déchiffrés avant d'exécuter la requête. Soit $x$ le numéro de sommet donné en entrée et $S$ la valeur obtenue lors de la dernière requête de type 3 ; alors le numéro de sommet déchiffré est $(x-1+S) \bmod {n} + 1$.

Sortie

Pour chaque requête de type 3, afficher la valeur calculée sur une ligne séparée, dans l'ordre où les requêtes sont données.

Contraintes

• $1 \le N \le 10^5$
• $1 \le Q \le 3 \times 10^5$
• $1 \le a, b \le N$
• $a \ne b$
• $1 \le c \le 10^8$

Exemples

Entrée 1

3 7
1 1 2 3
1 3 1 1
3 1
2 1 3
3 1
1 2 1 2
3 2

Sortie 1

4
0
0

Entrée 2

5 17
1 1 5 10
1 3 1 7
1 5 2 5
1 3 4 2
2 3 1
1 4 1 6
2 5 2
3 1
3 2
3 2
1 2 1 2
3 4
2 5 1
1 4 5 2
2 3 4
1 3 5 9
3 5

Sortie 2

18
2
0
0
9

Entrée 3

10 37
1 2 3 6428496
1 7 10 41603701
1 2 7 61903527
1 1 6 57606292
1 2 1 43682226
1 8 2 59090781
3 6
3 10
1 10 7 15269842
3 6
3 7
1 3 10 39799671
1 3 5 28501778
3 5
2 1 10
1 6 10 37641690
2 9 6
3 8
1 6 8 89420938
3 9
2 6 3
1 9 6 17757145
2 9 3
1 1 9 26575112
2 3 8
1 2 1 19670627
2 3 5
1 1 5 12760556
2 3 4
1 4 1 36949637
3 7
2 6 9
1 6 8 74850387
2 3 8
3 3
1 7 3 77007154
3 3

Sortie 3

274612258
215521477
187109093
171839251
211638922
68332023
151324465
224010174
0
223740409