给定一棵包含 $N$ 个顶点的树。两个顶点之间的距离定义为它们之间简单路径上的边数。

共有 $Q$ 次询问。每次询问由两个顶点 $u$ 和 $v$ 以及一个整数 $d$ 指定。如果一对顶点之间的距离不小于 $d$，则称该顶点对是“好的”。在每一步中，你只能在“好的”顶点对之间移动。现在你的任务是计算从 $u$ 到 $v$ 所需的最少步数。如果无法到达目的地，则答案为 $-1$。

为了增加难度，题目给出了大量的询问。

输入格式

第一行包含三个整数 $N, Q$ 和 $M$：顶点数、询问数以及 $d$ 的上限。($1 \le N \le 2 \cdot 10^5, 1 \le Q \le 10^6, 1 \le M \le 2 \cdot 10^5$)。

第二行包含 $N-1$ 个整数 $f_2, f_3, \dots, f_N$，表示对于每个 $2 \le i \le N$，树中存在一条连接顶点 $i$ 和 $f_i$ 的边 ($1 \le f_i < i$)。

第三行包含六个整数 $u_1, v_1, d_1, A, B$ 和 $C$ ($1 \le u_1, v_1 \le N, 0 \le d_1 < M, 10^4 \le A, B, C \le 2 \cdot 10^4$)。

第一次询问由 $u_1, v_1$ 和 $d_1$ 指定。

第 $i$ 次 ($2 \le i \le Q$) 询问由 $u_i, v_i$ 和 $d_i$ 指定，生成规则如下：

• $u_i = ((A \cdot u_{i-1} + B + ans_{i-1}) \pmod N) + 1$
• $v_i = ((B \cdot v_{i-1} + C + ans_{i-1}) \pmod N) + 1$
• $d_i = (C \cdot d_{i-1} + A + ans_{i-1}) \pmod M$

其中 $ans_k$ 是第 $k$ 次询问的答案。

输出格式

输出整数 $$S = \sum_{i=1}^{Q} i \cdot (ans_i + 1)$$

样例

样例输入 1

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

样例输出 1

55