Bajtazar recibió como regalo por el día del número $\pi$ un bosque (un grafo acíclico no dirigido) con $n$ vértices. En este bosque, los vértices están numerados con números del $1$ al $n$, y las aristas tienen asignadas longitudes enteras positivas. Además, cada vértice tiene un color descrito por un número entero. Inicialmente, todos los vértices tienen el color $0$.

Como tú eres la persona que le dio este regalo a Bajtazar, tu tarea ahora es responder a las consultas de Bajtazar sobre este bosque. Cada consulta es de uno de los siguientes tipos:

• $1 \ a_i \ b_i \ d_i$ – Bajtazar añade al bosque una arista no dirigida de longitud $d_i$ que conecta los vértices $a_i$ y $b_i$. Se garantiza que el grafo, tras añadir esta arista, seguirá sin contener ciclos.
• $2 \ a_i \ b_i$ – Bajtazar elimina del bosque la arista que conecta los vértices $a_i$ y $b_i$.
• $3 \ v_i \ z_i \ k_i$ – Bajtazar vuelve a pintar de color $k_i$ todos los vértices alcanzables desde el vértice $v_i$ y que se encuentran a una distancia de él de como máximo $z_i$. La distancia entre dos vértices se define aquí como la suma de las longitudes de las aristas en el camino simple entre ellos.
• $4 \ u_i$ – Bajtazar te pregunta por el color actual del vértice $u_i$.

Entrada

La primera línea de la entrada contiene tres números enteros $n$, $m$ y $q$ ($2 \le n \le 200\,000$; $0 \le m \le n - 1$; $1 \le q \le 200\,000$), que representan, respectivamente, el número de vértices en el bosque, el número de aristas que se encuentran inicialmente en él y el número de consultas.

En las siguientes $m$ líneas de la entrada se encuentran las descripciones de las aristas del bosque. En la $i$-ésima de estas líneas hay tres números enteros $a_i$, $b_i$ y $d_i$ ($1 \le a_i, b_i \le n$; $1 \le d_i \le 10^9$), que indican que los vértices $a_i$ y $b_i$ están conectados por una arista de longitud $d_i$.

En las siguientes $q$ líneas de la entrada se encuentran las descripciones de las consultas en el formato dado en el enunciado del problema. En todas las consultas se cumple que $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}$ y $1 \le k_i \le 10^9$.

Se garantiza que las $m$ aristas dadas describen un bosque válido, que el grafo sigue siendo un bosque válido después de cada modificación y que nunca aparecerá una consulta que ordene eliminar una arista que no esté presente actualmente en el bosque.

Se garantiza también que aparecerá al menos una consulta del cuarto tipo.

Salida

La salida debe contener tantas líneas como consultas del cuarto tipo hubo en la entrada. Cada una de ellas debe contener un único número entero: el color del vértice por el que preguntó Bajtazar.

Ejemplos

Entrada 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

Salida 1

0
5
3
0
0

Subtareas

• En algunos grupos de pruebas no hay consultas del primer ni del segundo tipo y se cumple $m = n - 1$.
• En algunos grupos de pruebas, en todas las consultas del tercer tipo se cumple $z_i = 10^{15}$.

Para cada uno de los casos mencionados anteriormente existe al menos un grupo que lo cumple. Los grupos para ambas condiciones pueden ser disjuntos o no.