시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB42250.000%

문제

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{.}$$

예제 입력 1

6 9 5
1 2 1 3 3
6 3 0 10865 16947 15183

예제 출력 1

55