À l'occasion de la journée de la constante $\pi$, Bajtazar a reçu en cadeau une forêt (un graphe acyclique non orienté) composée de $n$ sommets. Dans cette forêt, les sommets sont numérotés de $1$ à $n$ et les arêtes ont des longueurs entières positives. De plus, chaque sommet possède une couleur représentée par un entier. Initialement, tous les sommets ont la couleur $0$.

Comme c'est vous qui avez offert ce cadeau à Bajtazar, votre tâche consiste désormais à répondre aux requêtes de Bajtazar concernant cette forêt. Chaque requête est de l'un des types suivants :

• $1 \ a_i \ b_i \ d_i$ – Bajtazar ajoute à la forêt une arête non orientée de longueur $d_i$ reliant les sommets $a_i$ et $b_i$. Il est garanti que le graphe ne contiendra toujours pas de cycle après l'ajout de cette arête.
• $2 \ a_i \ b_i$ – Bajtazar supprime de la forêt l'arête reliant les sommets $a_i$ et $b_i$.
• $3 \ v_i \ z_i \ k_i$ – Bajtazar repeint avec la couleur $k_i$ tous les sommets accessibles depuis le sommet $v_i$ et situés à une distance inférieure ou égale à $z_i$ de celui-ci. La distance entre deux sommets est définie ici comme la somme des longueurs des arêtes sur le chemin unique les reliant.
• $4 \ u_i$ – Bajtazar vous demande la couleur actuelle du sommet $u_i$.

Entrée

La première ligne de l'entrée contient trois entiers $n$, $m$ et $q$ ($2 \le n \le 200\,000$; $0 \le m \le n - 1$; $1 \le q \le 200\,000$), représentant respectivement le nombre de sommets dans la forêt, le nombre d'arêtes initialement présentes et le nombre de requêtes.

Les $m$ lignes suivantes contiennent les descriptions des arêtes de la forêt. La $i$-ième de ces lignes contient trois entiers $a_i$, $b_i$ et $d_i$ ($1 \le a_i, b_i \le n$; $1 \le d_i \le 10^9$), signifiant que les sommets $a_i$ et $b_i$ sont reliés par une arête de longueur $d_i$.

Les $q$ lignes suivantes contiennent les descriptions des requêtes dans le format indiqué dans l'énoncé. Pour toutes les requêtes, on a $1 \le a_i, b_i, v_i, u_i \le n$, $1 \le d_i \le 10^9$, $0 \le z_i \le 10^{15}$ et $1 \le k_i \le 10^9$.

Il est garanti que les $m$ arêtes fournies décrivent une forêt valide, que le graphe reste une forêt valide après chaque modification, et qu'il n'y aura jamais de requête demandant la suppression d'une arête qui n'est pas actuellement dans la forêt.

Il est également garanti qu'il y aura au moins une requête de type quatre.

Sortie

La sortie doit contenir autant de lignes qu'il y avait de requêtes de type quatre dans l'entrée. Chacune d'elles doit contenir un seul entier : la couleur du sommet interrogé par Bajtazar.

Exemples

Entrée 1

4 2 9
1 2 2
3 2 5
4 2
3 2 2 5
4 1
3 2 4 3
4 1
4 3
2 2 1
1 1 4 1
4 4

Sortie 1

0
5
3
0
0

Sous-tâches

• Dans certains groupes de tests, il n'y a pas de requêtes de type un ou deux, et $m = n - 1$.
• Dans certains groupes de tests, pour toutes les requêtes de type trois, $z_i = 10^{15}$.

Pour chacun des cas mentionnés ci-dessus, il existe au moins un groupe qui le satisfait. Ces groupes peuvent être disjoints ou non pour les deux conditions.