For a tree with $n$ vertices rooted at $1$, where $p_i$ is the direct parent of vertex $i$ and $a_i$ is the weight of vertex $i$. We define $p_1 = 0$.
Define the function $f(x, y)$ as follows for vertices $x$ and $y$ at the same depth:
- Initialize $\text{ans} = 0$.
- While $x$ and $y$ are still not equal to $0$:
+ $\text{ans} \leftarrow \text{ans} + a_x \times a_y$.
+ $x \leftarrow p_x$.
+ $y \leftarrow p_y$.
- $f(x, y)$ is the value of $\text{ans}$.
You need to process $q$ queries, each query being two integers $x, y$. Calculate $f(x, y)$ for each query.
The depth of a vertex is the number of edges on the simple path from the root to that vertex.
### Input
- The first line contains two integers $n, q$.
- The second line contains $n$ integers $a_i$.
- The third line contains $n-1$ integers $p_2, p_3, ..., p_n$.
- The next $q$ lines each contain two integers $x, y$, representing a query. Ensure that $x, y$ are at the same depth.
### Output
- For each query, print an integer representing $f(x, y)$.
### Constraints
- $1 \le n \le 10^5$.
- $1 \le q \le 10^5$.
- $1 \le a_i \le 10^5$.
- $1 \le p_i < i$.
### Example
Input:
```
14 8
3 2 5 3 1 4 2 2 2 5 5 5 2 4
1 2 3 1 1 4 7 3 3 1 5 3 8
4 4
4 10
13 10
3 12
13 9
3 12
9 10
11 5
```
Output:
```
47
53
48
36
42
36
48
14
```
