Problem J
Justice for Ants

Chimera Ant is an intelligent and hard-working species.

There is a colony of Chimera Ants living in Danang, Vietnam. With careful infrastructure planning and hard work, they have built their kingdom with $n$ towns, numbered from $1$ to $n$. The towns are connected by $n - 1$ two-way roads, such that, there is exactly one simple path between any pair of towns.

Winter is coming! The Chimera Ant Queen is planning to distribute food to the $n$ towns: the $i$-th town will receive $a_ i$ units of food.

However, the ants feel that the plan is not fair. The ants demand justice! They submit $q$ requests. In each request, $4$ towns $\ell $, $r$, $u$ and $v$ are given, such that the distance from $\ell $ to $r$ and from $u$ to $v$ are equal. Here the distance from town $a$ to town $b$ is the number of edges on the only simple path from $a$ to $b$.

Let $p_1 = u, p_2, \ldots , p_{\ell } = v$ denotes the simple path between town $u$ and town $v$; $q_1 = x, q_2, \ldots , q_{\ell } = y$ denotes the simple path between town $x$ and town $y$. The request says that for every $i$ between $1$ and $\ell $, town $p_ i$ and town $q_ i$ receive the same amount of food.

Changing the food distribution plan turns out to be a difficult problem. The Chimera Ant Queen has a non-negative integer $k$, and each second, she can change the plan by applying the following steps:

• Select an integer $t$.

• Select a town $i$.

• Either decrease or increase the amount of food distributed to town $i$ by $t \cdot k + 1$. In other words, the Chimera Ant Queen can either set $a_ i := a_ i + (t \cdot k + 1)$ or $a_ i := a_ i - (t \cdot k + 1)$. After this step, $a_ i$ must be a non-negative integer, as we cannot distribute a negative amount of food.

What is the shortest time it would take for the Chimera Ant Queen to change the food distribution plan to satisfy all the requests?

Input

The first line of input contains $3$ integers $n$, $q$ and $k$ — the number of towns, the number of requests and the integer the Chimera Ant Queen has $(1 \le n \le 5 \cdot 10^5, 1 \le q \le 2 \cdot 10^5, 0 \le k \le 10^6)$.

The second line contains $n$ integers, $a_1, a_2, \ldots , a_ n$ $(1 \le a_ i \le 10^9)$, where $a_ i$ is the initial amount of food distributed to town $i$.

The next $n - 1$ lines contain $n - 1$ integers $p_2, p_3, \ldots p_ n$ $(1 \leq p_ i < i)$, one on each line, meaning that there is a two-way road connecting town $p_ i$ and town $i$.

Each of the next $q$ lines contains $4$ integers $u$, $v$, $x$ and $y$, describing one request $(1 \le u, v, x, y \le n)$. It is guaranteed that the two simple paths from $u$ to $v$ and from $x$ to $y$ have equal length.

The input guarantees that there is exactly one simple path between any pair of towns, and it is possible to satisfy all $q$ requests.

Output

Output a single integer — the minimum number of seconds it would take for the Chimera Ant Queen to change the food distribution plan.

Explanation of Sample input

There are $4$ roads: $(1, 2)$, $(1, 3)$, $(3, 4)$ and $(3, 5)$.

Since $k = 0$, in each second, the Chimera Ant Queen can either increase or decrease $a_ i$ by $1$.

An optimal solution would be to reduce $a_1$ to $1$ and $a_4$ to $1$, which would take $3$ seconds.

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

3