Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E. Noble Knight's Path

time limit per test

4 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputIn 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.

- The barbarians attacked castle
*c*. The interesting fact is, the barbarians never attacked the same castle twice throughout the whole Berlandian history. - 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.

Input

The first input line contains integer *n* (2 ≤ *n* ≤ 10^{5}) — 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* ≤ 10^{5}) — 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.

Output

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.

Examples

Input

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

Output

2

-1

-1

2

Input

6

2 5 2 2 0 5

3

2 1 6 2 0

1 2

2 4 5 1 0

Output

5

-1

Note

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.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/13/2018 22:18:43 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|