Flight

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

There are $Q$ queries. Each query is specified by two vertices $u$ and $v$ and an integer $d$. A pair of vertices is called good if the distance between them is not less than $d$. In each step, you can only move between a good pair of vertices. Now your task is to calculate the minimum number of steps you have to make in order to get from $u$ to $v$. If you can not reach the destination, the answer is $-1$.

A lot of queries are given to you to make this problem difficult.

The first line of input 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$ which mean that, for every $i$ such that $2 \leq i \leq N$, there is an edge between vertices $i$ and $f\_i$ in the tree ($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 specified by $u\_1$, $v\_1$ and $d\_1$.

The $i$-th ($2 \leq i \leq Q$) query is specified by $u\_i$, $v\_i$ and $d\_i$ which are generated by the following rules:

• $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 for query $k$.

Output the integer $S = \sum\limits\_{i = 1}^{Q} i \cdot (\mathit{ans}\_i + 1)\text{.}$