eolymp
bolt
Try our new interface for solving problems
Problems

Magic Roads

Magic Roads

Time limit 2 seconds
Memory limit 128 MiB

You are trapped in the Magic Country. It turned out that Magic Country has the same structure as an ordinary one. There are cities in it, and some of them are connected by bidirectional roads. Each road has its own length, and by some Magical Coincidence all lengths are unique.

But, unlike a king of some ordinary country, the King of the Magic Country can do all he wants. He may order to build some road, and may order to break another one. But such simple orders bored him a long time ago... Recently, the King has found a new game: sometimes he issues a decree by which all the roads from some city change their states to the opposite. There are only two states: either a road is in use or it isn't.

You came to the King. He was in a good mood and decided to play with you. King issued decrees and occasionally turned to you with a question. At first he wanted to ask: "what is the shortest road from all roads that are now in use in the Magic Country?". But then he realized that it was too easy. And he decided to ask the following question: "what is the k-th shortest road from all roads that are in use now, if it exists?".

Since he was the King of Magic Country (where the sun always shines on the rainbow fields), he decided to chop off your head if your answer was incorrect. For this reason, you have to answer correctly to all his questions.

Input data

The first line contains three integers n, m and q (2n500, 1mn * (n - 1) / 2, 1q200000): the number of cities, the number of roads and the number of King's actions. Each of the next m lines contains three integers a[i], b[i] and c[i] (1a[i], b[i]n, 1c[i]10^9): the numbers of cities connected by i-th road and the length of this road.

It is guaranteed that there will be no more than one road between any two cities and no road that connects city to itself. Additionally, all road lengths are unique. Initially, all roads are considered to be in use.

Next q lines describe the King's actions. The first integer x[i] in each line describes the type of action. If x[i] = 1, it means issuing a new decree. In that case, it is followed by an integer v[i] (1v[i] n): the number of city, for which this decree is issued. If x[i] = 2, it means the King has a question for you. In that case, it is followed by an integer k[i] (1k[i]m).

Output data

For each King's question, you should print a line consisting of one integer: the answer to that question. Answer to the question is the number of k[i]-th shortest road from the set of roads which are in use at that moment. Roads are numbered in the order in which they are given in the input. If at some point there are less than k[i] roads, output -1 instead of the number of k[i]-th shortest road.

Examples

Input example #1
5 6 7
1 2 5
1 4 3
1 5 1
2 3 6
2 4 4
4 5 2
2 3
1 1
2 3
1 2
2 3
2 1
2 2
Output example #1
2
4
-1
6
1
Input example #2
2 1 4
1 2 1
1 1
2 1
1 2
2 1
Output example #2
-1
1
Source 2013 Petrozavodsk, Moscow SU ST + NNSU Contest, Day 2, August 24, Problem E