Магические дороги
Вы попали в волшебную страну. Оказалось, что структура магической страны такова же как и обычной. Она содержит несколько городов, некоторые из которых соединены двунаправленными дорогами. Каждая дорога имеет свою длину, и по некоторому магическому совпадению все длины дорог разные.
Однако в отличии от обычного королевства, в волшебном король может делать все что захочет. Он может приказать построить дороги, а может их и разрушить. Однако приказы такого типа для него за длительное время очень наскучили... Недавно король придумал новую игру: недавно он издал декрет, согласно которому все дороги, исходящие из одного города, меняют свои состояния на противоположные. Каждая дорога имеет два состояния: либо она используется, либо нет.
Вы пришли к королю. Он был в хорошем настроении и решил поиграть с Вами. Король издал указы и внезапно обратился к Вам с вопросом. Сначала он хотел спросить: "какова длина самой короткой дороги среди всех дорог в волшебной стране?". Однако вскоре он решил, что это простой вопрос. И он придумал следующий вопрос: "Найти k-ую кратчайшую дорогу среди всех тех, которые на данный момент используется (если такая существует)".
Поскольку он был королем волшебной страны (где солнце всегда светит на радужные поля), то решил отрубить Вам голову если ответ будет неправильным. Поэтому Вам придется ответить правильно на все вопросы.
Входные данные
Первая строка содержит три целых числа n, m и q (2 ≤ n ≤ 500, 1 ≤ m ≤ n * (n - 1) / 2, 1 ≤ q ≤ 200000): количество городов, количество дорог и число запросов короля. Каждая из следующих m строк содержит три целых числа a[i], b[i] и c[i] (1 ≤ a[i], b[i] ≤ n, 1 ≤ c[i] ≤ 10^9): номера городов, соединенных i-ой дорогой и длина дороги.
Гарантируется, что между любой парой городов существует не более одной дороги, и никакая дорога не ведет сама в себя. Все длины дорог различны. Сначала все дороги считаются используемыми.
Следующие q строк описывают действия короля. Первое число x[i] в каждой строке содержит тип действия. Если x[i] = 1, то происходит издание нового указа. Далее идет число v[i] (1 ≤ v[i] ≤ n) - номер города, в котором издается указ. Если x[i] = 2, то король задает Вам вопрос. В этом случае далее следует целое число k[i] (1 ≤ k[i] ≤ m).
Выходные данные
Для каждого вопроса короля следует вывести строку, содержащую одно число - ответ на вопрос. Ответом должна быть длина k[i]-ой кратчайшей дороги из множества используемых на данный момент дорог. Дороги нумеруются в том же порядке, в каком они задаются на входе. Если в какой-то момент имеется меньше k[i] дорог, то вывести -1 на запрос о k[i]-ой кратчайшей дороге.