Flight

You are given a tree with $N$ vertices. The distance between two vertices is the number of edges on the simple path between them.

There are $Q$ queries. Each query gives two vertices $u$ and $v$ and an integer $d$. A pair of vertices is called good if the distance between them is at least $d$. In each step, you can only move between a good pair of vertices. Find the minimum number of steps needed to get from $u$ to $v$. If the destination cannot be reached, the answer is $-1$.

The queries are generated from a formula, so there are many of them.

The first line contains three integers $N$, $Q$, and $M$: the number of vertices, the number of queries, and the upper bound for $d$. ($1 \leq N \leq 2 \cdot 10^5$, $1 \leq Q \leq 10^6$, $1 \leq M \leq 2 \cdot 10^5$).

The second line contains $N - 1$ integers $f_2$, $f_3$, $\ldots$, $f_N$. For every $i$ with $2 \leq i \leq N$, there is an edge between vertices $i$ and $f_i$ ($1 \leq f_i < i$).

The third line contains six integers $u_1$, $v_1$, $d_1$, $A$, $B$, and $C$ ($1 \leq u_1, v_1 \leq N$, $0 \leq d_1 < M$, $10^4 \leq A, B, C \leq 2 \cdot 10^4$). The first query is given by $u_1$, $v_1$, and $d_1$.

For $2 \leq i \leq Q$, the $i$-th query is generated as follows:

$u_i = ((A \cdot u_{i-1} + B + \mathit{ans}_{i-1}) \bmod N) + 1$,

$v_i = ((B \cdot v_{i-1} + C + \mathit{ans}_{i-1}) \bmod N) + 1$,

$d_i = (C \cdot d_{i-1} + A + \mathit{ans}_{i-1}) \bmod M$.

Here, $\mathit{ans}_k$ is the answer to query $k$.

Output the integer

$S = \sum_{i=1}^{Q} i \cdot (\mathit{ans}_i + 1)$