Meeting Place

Bessie and Jonell are great friends. Because Farmer John shuffles where the cows graze every day, they sometimes end up far apart and cannot talk.

The pastures and paths on the farm form a tree: between any two pastures there is exactly one path, and every pasture except pasture $1$ (the root) has exactly one parent pasture.

Whenever they want to gossip, Bessie and Jonell agree to meet at the closest pasture that is an ancestor of both Bessie's pasture and Jonell's pasture. A pasture is considered an ancestor of itself, so if one of them is already an ancestor of the other, they simply meet at that pasture.

The farm has $N$ pastures ($1 \le N \le 1000$), numbered $1$ through $N$. For every pasture except pasture $1$ you are given its parent $P_i$ ($1 \le P_i \le N$). Over the next $M$ days ($1 \le M \le 1000$), on day $k$ Bessie is in pasture $B_k$ and Jonell is in pasture $J_k$ ($1 \le B_k, J_k \le N$). For each day, report their meeting place.

For example, consider the following farm, where pasture $1$ is the root:

         [1]
       /  |  \
     [2] [3] [6]
     /        |  \
   [4]      [8]  [9]
           /  \
         [5]  [7]

In this farm the meeting place for pastures $7$ and $5$ is pasture $8$ (their closest common ancestor), and the meeting place for pastures $2$ and $7$ is pasture $1$.

• Line $1$: two space-separated integers $N$ and $M$.
• Lines $2 \dots N$: line $i$ contains a single integer $P_i$, the parent of pasture $i$.
• Lines $N+1 \dots N+M$: line $N+k$ contains two space-separated integers $B_k$ and $J_k$, Bessie's and Jonell's pastures on day $k$.

• Lines $1 \dots M$: line $k$ contains a single integer, the meeting place for Bessie and Jonell on day $k$.