CF226E.Noble Knight's Path

In Berland each feudal owns exactly one castle and each castle belongs to exactly one feudal.

Each feudal, except one (the King) is subordinate to another feudal. A feudal can have any number of vassals (subordinates).

Some castles are connected by roads, it is allowed to move along the roads in both ways. Two castles have a road between them if and only if the owner of one of these castles is a direct subordinate to the other owner.

Each year exactly one of these two events may happen in Berland.

1. The barbarians attacked castle c. The interesting fact is, the barbarians never attacked the same castle twice throughout the whole Berlandian history.
2. A noble knight sets off on a journey from castle a to castle b (provided that on his path he encounters each castle not more than once).

Let's consider the second event in detail. As the journey from a to b is not short, then the knight might want to stop at a castle he encounters on his way to have some rest. However, he can't stop at just any castle: his nobility doesn't let him stay in the castle that has been desecrated by the enemy's stench. A castle is desecrated if and only if it has been attacked after the year of y. So, the knight chooses the k-th castle he encounters, starting from a (castles a and b aren't taken into consideration), that hasn't been attacked in years from y + 1 till current year.

The knights don't remember which castles were attacked on what years, so he asked the court scholar, aka you to help them. You've got a sequence of events in the Berland history. Tell each knight, in what city he should stop or else deliver the sad news — that the path from city a to city b has less than k cities that meet his requirements, so the knight won't be able to rest.

在贝尔兰，每位封建领主恰好拥有一座城堡，且每座城堡恰好属于一位封建领主。

除一人（国王）外，每位封建领主都直接隶属于另一位封建领主。一位封建领主可以拥有任意数量的附庸（即直接下属）。

若干城堡之间由道路连接，道路为双向通行。当且仅当其中一座城堡的所有者是另一座城堡所有者的直接下属时，这两座城堡之间才存在一条道路。

每年，在贝尔兰恰好发生以下两种事件之一：

1. 野蛮人袭击了城堡 $c$。有趣的是，在整个贝尔兰历史中，野蛮人从未两次袭击同一座城堡。
2. 一位高贵的骑士从城堡 $a$ 出发，前往城堡 $b$（要求其路径上每个城堡至多经过一次）。

我们详细考察第二种事件。由于从 $a$ 到 $b$ 的旅程不短，骑士可能希望在途中某座城堡稍作休憩。然而，他不能随意选择任何城堡停留：他的高贵品性不允许他停留在已被敌人恶臭玷污的城堡中。一座城堡被玷污，当且仅当它在第 $y$ 年之后（即从第 $y+1$ 年起直至当前年份）曾遭到过袭击。因此，骑士将从 $a$ 出发沿路径依次计数，选择第 $k$ 座满足条件的城堡作为休憩点（注意：起点 $a$ 和终点 $b$ 均不计入计数），该城堡必须未在第 $y+1$ 年至当前年份之间遭受过袭击。

骑士们并不记得各城堡在哪些年份遭到了袭击，因此他们向宫廷学者（也就是你）求助。你已获得贝尔兰历史上的一系列事件记录。请针对每位骑士，告知他应在哪个城市休憩；若从城市 $a$ 到城市 $b$ 的路径上，满足上述条件的城市少于 $k$ 座，则只能遗憾地告知他：无法找到合适的休憩地点。

The first input line contains integer n (2 ≤ n ≤ 105) — the number of feudals.

The next line contains n space-separated integers: the i-th integer shows either the number of the i-th feudal's master, or a 0, if the i-th feudal is the King.

The third line contains integer m (1 ≤ m ≤ 105) — the number of queries.

Then follow m lines that describe the events. The i-th line (the lines are indexed starting from 1) contains the description of the event that occurred in year i. Each event is characterised by type t__i (1 ≤ t__i ≤ 2). The description of the first type event looks as two space-separated integers t__i c__i (t__i = 1; 1 ≤ c__i ≤ n), where c__i is the number of the castle that was attacked by the barbarians in the i-th year. The description of the second type contains five space-separated integers: t__i a__i b__i k__i y__i (t__i = 2; 1 ≤ a__i, b__i, k__i ≤ n; a__i ≠ b__i; 0 ≤ y__i < i), where a__i is the number of the castle from which the knight is setting off, b__i is the number of the castle to which the knight is going, k__i and y__i are the k and y from the second event's description.

You can consider the feudals indexed from 1 to n. It is guaranteed that there is only one king among the feudals. It is guaranteed that for the first type events all values c__i are different.

第一行输入包含一个整数 $n$（$2 \leq n \leq 10^5$）—— 封建领主的数量。

第二行包含 $n$ 个用空格分隔的整数：其中第 $i$ 个整数表示第 $i$ 位封建领主的直属领主编号；若该值为 $0$，则表示第 $i$ 位封建领主即为国王。

第三行输入包含一个整数 $m$（$1 \leq m \leq 10^5$）—— 查询事件的数量。

接下来是 $m$ 行，描述按年份依次发生的事件。第 $i$ 行（行号从 $1$ 开始）描述第 $i$ 年发生的事件。每个事件由类型 $t_i$（$1 \leq t_i \leq 2$）刻画。第一类事件的描述为两个用空格分隔的整数 $t_i\ c_i$（其中 $t_i = 1$；$1 \leq c_i \leq n$），其中 $c_i$ 表示第 $i$ 年遭蛮族袭击的城堡编号。第二类事件的描述为五个用空格分隔的整数：$t_i\ a_i\ b_i\ k_i\ y_i$（其中 $t_i = 2$；$1 \leq a_i, b_i, k_i \leq n$；$a_i \neq b_i$；$0 \leq y_i < i$），其中 $a_i$ 是骑士出发的城堡编号，$b_i$ 是骑士前往的城堡编号，$k_i$ 和 $y_i$ 即第二类事件描述中所指的 $k$ 和 $y$。

可认为封建领主编号为 $1$ 至 $n$。保证所有封建领主中仅有一位国王。保证所有第一类事件中的 $c_i$ 值互不相同。

For each second type event print an integer — the number of the castle where the knight must stay to rest, or -1, if he will have to cover the distance from a__i to b__i without a rest. Separate the answers by whitespaces.

Print the answers in the order, in which the second type events are given in the input.

对于每个第二类事件，输出一个整数——骑士必须停留休息的城堡编号；如果他必须从 $a_i$ 到 $b_i$ 不休息地完成全程，则输出 -1。各答案之间用空格分隔。

请按照输入中第二类事件出现的顺序输出答案。

In the first sample there is only castle 2 on the knight's way from castle 1 to castle 3. When the knight covers the path 1 - 3 for the first time, castle 2 won't be desecrated by an enemy and the knight will stay there. In the second year the castle 2 will become desecrated, so the knight won't have anywhere to stay for the next two years (as finding a castle that hasn't been desecrated from years 1 and 2, correspondingly, is important for him). In the fifth year the knight won't consider the castle 2 desecrated, so he will stay there again.

在第一个样例中，骑士从城堡 1 前往城堡 3 的路径上仅有城堡 2。当骑士首次走完路径 $1\text{--}3$ 时，城堡 2 尚未被敌人亵渎，因此骑士将停留于此。第二年，城堡 2 将被亵渎，因此接下来两年骑士将无处可居（因为对他而言，分别在第 1 年和第 2 年找到一座尚未被亵渎的城堡至关重要）。到了第五年，骑士将不再视城堡 2 为被亵渎状态，因此他将再次停留于此。