E. Путь благородного рыцаря
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В Берляндии каждый феодал владеет ровно одним замком, а каждый замок принадлежит ровно одному феодалу.

Каждый феодал, кроме одного (короля), находится в подчинении у другого феодала. Вассалов (подчиненных) у феодала может быть любое количество.

Некоторые замки соединены дорогами, по которым разрешено движение в обе стороны. Между двумя замками есть дорога в том и только в том случае, если владелец одного из этих замков находится в непосредственном подчинении у владельца другого.

Каждый год в Берляндии может случиться ровно одно из двух событий.

  1. На замок номер с напали варвары. Известно, что за всю историю Берляндии варвары никогда не нападали на один и тот же замок дважды.
  2. Благородный рыцарь отправился в путешествие из замка a в замок b (причем по такому пути, что каждый замок встречается на нем не более одного раза).

Остановимся подробнее на втором событии. Поскольку путь из a в b предстоит неблизкий, то, возможно, рыцарь захочет остановиться в замке, лежащем на его пути, чтобы отдохнуть. Но он может сделать остановку не в каждом замке: благородство не позволяет ему находиться в замке, оскверненном невыветрившимся духом врага. Замок считается оскверненным тогда и только тогда, когда на него совершалось нападение после года y. Поэтому выбор рыцаря остановится на k-м замке, лежащем на его пути, считая от a (сами замки a и b в счет не идут), на который не совершалось нападений в годы с y + 1 по текущий.

Рыцари плохо помнят, в какие годы и на какие замки совершались нападения, поэтому они обратились к придворному ученому, то есть к Вам, за помощью. Вам задана последовательность событий в истории Берляндии, сообщите каждому рыцарю, в каком городе ему следует остановиться, или огорчите его известием о том, что на пути из a в b меньше k городов, удовлетворяющих его требованиям, а потому отдыхать рыцарю не придется.

Входные данные

В первой строке входных данных записано целое число n (2 ≤ n ≤ 105) — количество феодалов.

В следующей строке записаны n целых чисел через пробел: i-е число равно номеру феодала, которому подчинен i-й, или 0, если номер i имеет король.

В третьей строке записано целое число m (1 ≤ m ≤ 105) — количество событий в истории Берляндии.

Далее идет m строк, описывающих события. В i-й из этих строк (нумерация ведется с 1) находится описание события, произошедшего в год i. Каждое событие характеризуется типом ti (1 ≤ ti ≤ 2). Описание события первого типа (нападение на замок): два целых числа, записанных через пробел, ti ci (ti = 1; 1 ≤ ci ≤ n), где ci — номер замка, на который напали варвары в i-ый год. Описание события второго типа (путешествие рыцаря): пять целых чисел, записанных через пробел, ti ai bi ki yi (ti = 2; 1 ≤ ai, bi, ki ≤ n; ai ≠ bi; 0 ≤ yi < i), где ai — номер замка, из которого отправляется в путь рыцарь, bi — номер замка, в который едет рыцарь, ki и yi — k и y из описания второго события.

Считайте, что феодалы пронумерованы от 1 до n. Гарантируется, что среди феодалов ровно один король. Гарантируется, что для событий первого типа все ci различны.

Выходные данные

Для каждого события второго типа выведите целое число — номер замка, в котором должен остановиться на отдых рыцарь, или -1, если ему придется проделать путь из ai в bi без остановок. Разделяйте ответы пробельными символами.

Ответы выводите в том порядке, в котором события второго типа заданы во входных данных.

Примеры
Входные данные
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
Входные данные
6
2 5 2 2 0 5
3
2 1 6 2 0
1 2
2 4 5 1 0
Выходные данные
5
-1
Примечание

В первом примере на пути рыцаря из замка 1 в замок 3 лежит только замок 2. Когда рыцарь проделает путь 1 - 3 в первый раз, замок 2 не будет осквернен врагом, поэтому именно в нем рыцарь и остановится. Во второй год замок 2 станет осквернен, а потому в следующие два года рыцарю будет негде остановиться (так как ему важно, чтобы замок не был осквернен, начиная с годов 1 и 2, соответственно). В пятый год рыцарь не будет считать замок 2 оскверненным, а потому вновь остановится в нем.