There is a tree with vertices and weighted paths. The following operations are required to be supported:

• Operation 0: delete the path with the smallest weight in the remaining.
• Operation 1: given a vertex , ask for the minimum weight among all the weighted paths that do not intersect with .

A path intersects with if and only if is one of the vertices in the shortest path from to (including and ).

输入描述:

The first line of input contains three positive integers  (), where  describes the number of operations.
The next  lines each of which contains two positive integers  (), representing a tree edge.
The next  lines, each line contains three integers  (), representing a path  with a weight of . It is guaranteed that the path weights are different from each other.
The next  lines, the first integer of each line  describes the type of the operation.
If , then follows an integer , which describes the vertex of the query as .
 is the answer of the last query operation, and its initial value is .  is the XOR symbol. It is guaranteed that , .

输出描述:

For each query, output a line with an integer describing the smallest weight.
Output  if all weighted paths that have not been deleted intersect the queried vertex or all paths have been deleted.

5 2 4
1 2
1 3
3 4
3 5
1 3 1
3 5 2
1 3
1 -5
0
1 5

-1
1
2