For a tree with n vertices rooted at 1, where pi is the direct parent of vertex i and ai is the weight of vertex i. We define p1=0.
Define the function f(x,y) as follows for vertices x and y at the same depth:
- Initialize ans=0.
- While x and y are still not equal to 0:
+ ans←ans+ax×ay.
+ x←px.
+ y←py.
- f(x,y) is the value of 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 ai.
- The third line contains n−1 integers p2,p3,...,pn.
- 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≤n≤105.
- 1≤q≤105.
- 1≤ai≤105.
- 1≤pi<i.
### Example
Input:
148325314222555241231147331538444101310312139312910115
Output:
4753483642364814
