{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"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.\r\n\r\nBut, 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\u0027t.\r\n\r\nYou 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?\"_.\r\n\r\nSince 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.\r\n\r\n#### Input\r\nThe first line contains three integers **n**, **m** and **q** (**2** ≤ **n** ≤ **500**, **1** ≤ **m** ≤ **n** * (**n** - **1**) / **2**, **1** ≤ **q** ≤ **200000**): the number of cities, the number of roads and the number of King\u0027s actions. Each of the next **m** lines contains three integers `a[i]`, `b[i]` and `c[i]` (**1** ≤ `a[i]`, `b[i]` ≤ **n**, **1** ≤ `c[i]` ≤ `10^9`): the numbers of cities connected by **i**-th road and the length of this road.\r\n\r\nIt 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.\r\n\r\nNext **q** lines describe the King\u0027s actions. The first integer `x[i]` in each line describes the type of action. If `x[i]` \u003d **1**, it means issuing a new decree. In that case, it is followed by an integer `v[i]` (**1** ≤ `v[i] ` ≤ **n**): the number of city, for which this decree is issued. If `x[i]` \u003d **2**, it means the King has a question for you. In that case, it is followed by an integer `k[i]` (**1** ≤ `k[i]` ≤ **m**).\r\n\r\n#### Output\r\nFor each King\u0027s 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."}},{"title":"Example","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 6 7\n1 2 5\n1 4 3\n1 5 1\n2 3 6\n2 4 4\n4 5 2\n2 3\n1 1\n2 3\n1 2\n2 3\n2 1\n2 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n4\n-1\n6\n1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr\u003e\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2 1 4\n1 2 1\n1 1\n2 1\n1 2\n2 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e-1\n1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}