Bajtazar received a forest (an undirected acyclic graph) with $n$ vertices as a gift for Pi Day. In this forest, the vertices are numbered from $1$ to $n$, and the edges have assigned positive integer lengths. Additionally, each vertex has a color described by an integer. Initially, all vertices have color $0$.

Since you are the one who gave Bajtazar this gift, your task is to answer Bajtazar's queries regarding this forest. Each query is of one of the following types:

• $1 \ a_i \ b_i \ d_i$ – Bajtazar adds an undirected edge of length $d_i$ to the forest, connecting vertices $a_i$ and $b_i$. It is guaranteed that the graph will not contain a cycle after adding this edge.
• $2 \ a_i \ b_i$ – Bajtazar removes the edge connecting vertices $a_i$ and $b_i$ from the forest.
• $3 \ v_i \ z_i \ k_i$ – Bajtazar repaints all vertices reachable from vertex $v_i$ at a distance of at most $z_i$ from it to color $k_i$. The distance between two vertices is defined here as the sum of the lengths of the edges on the simple path between them.
• $4 \ u_i$ – Bajtazar asks you for the current color of vertex $u_i$.

Input

The first line of input contains three integers $n$, $m$, and $q$ ($2 \le n \le 200\,000$; $0 \le m \le n - 1$; $1 \le q \le 200\,000$), representing the number of vertices in the forest, the number of edges initially present in it, and the number of queries, respectively.

The next $m$ lines of input contain descriptions of the forest edges. The $i$-th of these lines contains three integers $a_i$, $b_i$, and $d_i$ ($1 \le a_i, b_i \le n$; $1 \le d_i \le 10^9$), meaning that vertices $a_i$ and $b_i$ are connected by an edge of length $d_i$.

The next $q$ lines of input contain descriptions of the queries in the format given in the problem description. In all queries, $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}$, and $1 \le k_i \le 10^9$.

It is guaranteed that the given $m$ edges describe a valid forest, the graph remains a valid forest after each modification, and there will never be a query requesting the removal of an edge that is not currently in the forest.

It is also guaranteed that there will be at least one query of the fourth type.

Output

The output should contain as many lines as there were queries of the fourth type in the input. Each of them should contain a single integer – the color of the vertex that Bajtazar asked about.

Examples

Input 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

Output 1

0
5
3
0
0

Subtasks

• In some test groups, there are no queries of the first or second type, and $m = n - 1$.
• In some test groups, for all queries of the third type, $z_i = 10^{15}$.

For each of the cases mentioned above, there exists at least one group that satisfies it. These groups for both conditions may or may not be disjoint.