Cai Caizi has given you a tree with $n$ nodes, labeled from $1$ to $n$.

The distance $d(a, b)$ between two nodes $a$ and $b$ in the tree is defined as the smallest non-negative integer $k$ such that there exists a sequence of nodes $v_0, v_1, \dots, v_k$ where $v_0 = a$, $v_k = b$, and for all $0 \leq i \leq k-1$, there is an edge between $v_i$ and $v_{i+1}$ in the tree.

There are $m$ queries. Each query consists of parameters $p_0, d_0, p_1, d_1$. Calculate:

$$\sum\limits_{d(p_0,a)\leq d_0}\sum\limits_{d(p_1,b)\leq d_1}d(a,b)$$

Input

The first line contains an integer $n$, representing the number of nodes in the tree.

The next line contains $n-1$ integers $f_2, f_3, \dots, f_n$, where $f_i$ indicates that there is an edge between $i$ and $f_i$ ($1 \leq f_i \leq i-1$).

The next line contains an integer $m$, representing the number of queries.

The next $m$ lines each describe a query: each line contains four integers $p_0, d_0, p_1, d_1$ ($1 \leq p_0, p_1 \leq n, 0 \leq d_0, d_1 \leq n-1$).

Output

Output $m$ lines, each containing the answer to the corresponding query.

Examples

Input 1

7
1 1 2 3 5 2
5
5 1 5 0
2 0 5 0
2 2 4 5
7 2 2 4
3 2 5 4

Output 1

2
3
69
57
70

Subtasks

Idea: nzhtl1477, Solution: ccz181078, Code: ccz181078, Data: ccz181078

For $100\%$ of the data, it is guaranteed that $1 \leq n \leq 10^5$ and $1 \leq m \leq 10^5$.