Bowser's Pipes

Interview

Time limit2sMemory limit1024 MB

Summary

Given pipes that form a functional graph ending at coin rooms, for each queried pipe find the pipe that reaches the same coin room with the fewest warp rooms, ties to smallest index.

Level: Medium4 of 10
Topics: Graph, DFS
Solved: No attempts yet

Problem

Princess Peach is in trouble again! Mario is on a quest to rescue her from Bowser. To save her, he has to collect a number of coins located in coin rooms under the surface. To get to a coin room, he must enter pipes on the surface, which send him to a room below.

Some pipes do not lead directly to a coin room. They lead to a warp room instead. A warp room may lead to other warp rooms, until Mario finally reaches a coin room. Once Mario chooses a pipe to enter, he is warped through the pipes without regaining control until he reaches a coin room.

Mario does not like getting warped. For this reason, he asks his brother Luigi for help. Luigi jumps down some of the pipes to find out which coin room each one ultimately leads to, and he shares this information with Mario.

Mario then shows off his rescue skills. He jumps down the pipe that leads to the same coin room Luigi found, but passes the fewest possible warp rooms on the way. This spares Mario from nausea and impresses Princess Peach.

Input

The first line of input contains an integer $N$ ( $0 < N \le 100\,000$ ), the combined number of pipes, warp rooms, and coin rooms. They are numbered from $0$ to $N-1$ . The second line contains $N$ space-separated values $F_i$ ( $-1 \le F_i < N$ ). $F_i$ is the number of the warp or coin room to which Mario is propelled when he enters the pipe or the warp room with number $i$ . $F_i = -1$ means Mario has finally reached a coin room. Each warp room has at least one pipe leading to it. Luigi is guaranteed to reach a coin room after a finite number of steps, no matter which pipe he jumps into.

The third line of input contains an integer $A$ ( $0 < A \le 100\,000$ ), the number of pipes Mario asks Luigi to jump into. The following line contains $A$ numbers $D_i$ ( $0 \le D_i < N$ ), each denoting the number of a pipe that Luigi enters.

Output

For each pipe that Luigi enters, find the coin room it leads to. Then print the number of the pipe Mario should enter. This is the pipe that leads to the same coin room but passes the smallest number of warp rooms on the way. In the case of a tie, print the pipe with the smallest number.

Examples1

Example 1
Input
```
6
-1 5 0 1 5 -1
2
2 3
```
Expected output
```
2
4
```