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