Recently, Angie's math teacher began teaching the class about trees (the graph theory kind, of course). As homework, he gave everyone a rooted tree of nodes (the root node is ) and asked them to do LCA queries on the tree (each query is in the form `x y`

, and its answer is the LCA of nodes and in the tree). **Since he didn't have the funds to make proper test data for his trees, he generated them randomly with the following algorithm: for every node , he picked a uniform random integer in the range to be its parent node.**

Angie is feeling very demotivated and doesn't want to do her work. Can you solve the queries for her?

#### Constraints

for all

#### Input Specification

The first line contains the integers and .

The second line contains integers , the parents of nodes respectively. Note that node does not have a parent as it's the root node of the tree.

The next lines each contain a query of the form `x y`

.

#### Output Specification

For each query, output its answer on a new line.

#### Sample Input

```
10 5
1 2 1 1 4 2 1 6 9
3 9
10 7
4 4
1 3
2 3
```

#### Sample Output

```
1
1
4
1
2
```

#### Explanation

The tree from the sample input:

## Comments