You are given a tree with $n$ weighted vertices labeled from $1$ to $n$ rooted at vertex $1$. The parent of vertex $i$ is $p_i$ and the weight of vertex $i$ is $a_i$. For convenience, define $p_1=0$.

For two vertices $x$ and $y$ of the same depth$^\dagger$, define $f(x,y)$ as follows:

• Initialize $\mathrm{ans}=0$.
• While both $x$ and $y$ are not $0$:
• $\mathrm{ans}\leftarrow \mathrm{ans}+a_x\cdot a_y$;
  • $x\leftarrow p_x$;
  • $y\leftarrow p_y$.
• $f(x,y)$ is the value of $\mathrm{ans}$.

You will process $q$ queries. In the $i$-th query, you are given two integers $x_i$ and $y_i$ and you need to calculate $f(x_i,y_i)$.

$^\dagger$ The depth of vertex $v$ is the number of edges on the unique simple path from the root of the tree to vertex $v$.

Input

The first line contains two integers $n$ and $q$ ($2 \le n \le 10^5$; $1 \le q \le 10^5$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^5$).

The third line contains $n-1$ integers $p_2, \ldots, p_n$ ($1 \le p_i \lt i$).

Each of the next $q$ lines contains two integers $x_i$ and $y_i$ ($1\le x_i,y_i\le n$). It is guaranteed that $x_i$ and $y_i$ are of the same depth.

Output

Output $q$ lines, the $i$-th line contains a single integer, the value of $f(x_i,y_i)$.

Note

Consider the first example:

In the first query, the answer is $a_4\cdot a_5+a_3\cdot a_3+a_2\cdot a_2+a_1\cdot a_1=3+4+25+1=33$.

In the second query, the answer is $a_6\cdot a_6+a_2\cdot a_2+a_1\cdot a_1=1+25+1=27$.