New breeds of underground bacteria help in terraforming Mars. The bacteria feed mainly on regular bread loafs which are baked in huge quantities on the Mars surface and subsequently dropped into a specially constructed pit. To distribute the bread evenly in the subsurface, the pit consists of nearly vertical tunnels arranged in a tree-like structure. Each tunnel ends either in a cave filled with bacterial colonies or in a gate which connects into one or more other downward tunnels. The gates are mechanized and each of them keeps open only one downward tunnel at a time. When a loaf falls through a gate into a downward tunnel, the gate closes the tunnel and opens another one, to which it is connected, for the next arriving loaf. Opening the downward tunnels works in a cyclic fashion: When a gate closes the last downward tunnel it again opens the one which was open first. The order of open downward tunnels in each gate is fixed. At most one of the gates is on the surface. All loafs falling through at least one tunnel also fall through this topmost gate. The exception to the described scheme is the situation when the topmost gate is completely closed for maintenace, all tunnels become inaccessible and the loafs remain at the surface. In this scenario, for formal reasons, the surface is considered to be a cave and simutaneously the only node in the whole pit.
When the system started operating, before any bread loaf was deposited in it, the first downward tunnel in each gate was open.
Both caves and gates are commonly denoted as nodes, each node is labeled by a unique integer.
Determine which cave did each bread loaf fall into, as they were subsequently dropped, one after another, into the pit.
The first input line contains two integers $N$, $Q$ ($1 \le N, Q \le 3 \cdot 10^5$), the number of all nodes (gates and caves) in the pit and the number of bread loafs dropped into the pit. The nodes are labeled by integers $0, 1, \dots , N - 1$, the surface gate node is labeled by $0$.
The second line contains $N - 1$ integers. The value of $i$’th integer on the line is the label of the predecessor of node $i$. The predecessor of a node is the closest gate from which a falling loaf arrives to node $i$. The second input line also encodes the order of open downward tunnels in each gate. When value $X$ appears on the $j$’th and $k$’th positions and $j < k$, the tunnel connecting X to j opens before the tunnel connecting $X$ to $k$ opens.
Print $Q$ lines. The $i$’th line should contain the label of the cave that received the $i$’th loaf dropped into the pit.
|Sample Input 1||Sample Output 1|
5 5 0 0 1 1
3 2 4 2 3
|Sample Input 2||Sample Output 2|
7 10 0 0 0 2 2 2
1 4 3 1 5 3 1 6 3 1