E. Random Tree Path Match
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a random generated tree rooted at $$$1$$$ with $$$n$$$ vertices and some queries. Here a tree is a connected graph in which there are no cycles.

Each vertex of the tree has a weight $$$W_i$$$.

Each query has $$$2$$$ vertices $$$(u, v)$$$. For each query, assume that array $$$a$$$ is the path from $$$1$$$ to $$$u$$$, and array $$$b$$$ is the path from $$$1$$$ to $$$v$$$, find $$$2$$$ subsequence with equal length from $$$a$$$ and $$$b$$$ respectively as $$$c$$$ and $$$d$$$, maximize the following value:

$$$$$$ \sum_{i=1}^{size_c} W_{c_i} \times W_{d_i} $$$$$$

The tree itself is generated as follows:

Generate_tree(n):
    for i := 2 -> n
        father[i] := random choose an integer from [1, i - 1]
    return father

p.s. A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements.

Input

The first line of the input consists of one single integer $$$n (1 \le n \le 10^5)$$$ — the size of the tree, note that $$$n$$$ is not randomly generated.

The next line consists of $$$n$$$ integers: $$$W_1,W_2, \dots ,W_n(1 \le W_i \le 10^6)$$$ — the weight of each vertex.

The next line consists of $$$n-1$$$ integers: $$$p_2, p_3, \dots , p_n(1 \le p_i \lt i)$$$ — $$$p_i$$$ denotes the father of vertex $$$i$$$. We start from vertex $$$2$$$, as vertex $$$1$$$ is the root.

The next line consists of one integer $$$q (1 \le q \le 10^5)$$$ — the number of queries.

The next $$$q$$$ lines, each consists of two integers $$$u,v(1 \le u,v \le n)$$$ — denoting a query.

Output

For each query, print the maximum value as described above in a line.

Example
Input
3
1 100 100
1 1
1
2 3
Output
10001
Note

For the query in Example, path $$$a$$$ equals to $$$[1, 2]$$$, path $$$b$$$ equals to $$$[1, 3]$$$, we can make $$$c=a$$$ and $$$d=b$$$, we get $$$1 \times 1 + 100 \times 100 = 10001$$$.