В Берляндии каждый феодал владеет ровно одним замком, а каждый замок принадлежит ровно одному феодалу.
Каждый феодал, кроме одного (короля), находится в подчинении у другого феодала. Вассалов (подчиненных) у феодала может быть любое количество.
Некоторые замки соединены дорогами, по которым разрешено движение в обе стороны. Между двумя замками есть дорога в том и только в том случае, если владелец одного из этих замков находится в непосредственном подчинении у владельца другого.
Каждый год в Берляндии может случиться ровно одно из двух событий.
- На замок номер с напали варвары. Известно, что за всю историю Берляндии варвары никогда не нападали на один и тот же замок дважды.
- Благородный рыцарь отправился в путешествие из замка a в замок b (причем по такому пути, что каждый замок встречается на нем не более одного раза).
Остановимся подробнее на втором событии. Поскольку путь из a в b предстоит неблизкий, то, возможно, рыцарь захочет остановиться в замке, лежащем на его пути, чтобы отдохнуть. Но он может сделать остановку не в каждом замке: благородство не позволяет ему находиться в замке, оскверненном невыветрившимся духом врага. Замок считается оскверненным тогда и только тогда, когда на него совершалось нападение после года y. Поэтому выбор рыцаря остановится на k-м замке, лежащем на его пути, считая от a (сами замки a и b в счет не идут), на который не совершалось нападений в годы с y + 1 по текущий.
Рыцари плохо помнят, в какие годы и на какие замки совершались нападения, поэтому они обратились к придворному ученому, то есть к Вам, за помощью. Вам задана последовательность событий в истории Берляндии, сообщите каждому рыцарю, в каком городе ему следует остановиться, или огорчите его известием о том, что на пути из a в b меньше k городов, удовлетворяющих его требованиям, а потому отдыхать рыцарю не придется.
Выходные данные
Для каждого события второго типа выведите целое число — номер замка, в котором должен остановиться на отдых рыцарь, или -1, если ему придется проделать путь из ai в bi без остановок. Разделяйте ответы пробельными символами.
Ответы выводите в том порядке, в котором события второго типа заданы во входных данных.
Примечание
В первом примере на пути рыцаря из замка 1 в замок 3 лежит только замок 2. Когда рыцарь проделает путь 1 - 3 в первый раз, замок 2 не будет осквернен врагом, поэтому именно в нем рыцарь и остановится. Во второй год замок 2 станет осквернен, а потому в следующие два года рыцарю будет негде остановиться (так как ему важно, чтобы замок не был осквернен, начиная с годов 1 и 2, соответственно). В пятый год рыцарь не будет считать замок 2 оскверненным, а потому вновь остановится в нем.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
0 1 2
5
2 1 3 1 0
1 2
2 1 3 1 0
2 1 3 1 1
2 1 3 1 2
|
2
-1
-1
2
|
|
2
|
6
2 5 2 2 0 5
3
2 1 6 2 0
1 2
2 4 5 1 0
|
5
-1
|