LCA - 2#3299

LCA - 2

6 seconds

128 megabytes

Easy

You are given a rooted tree with $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5) vertices, numbered from $0$ to $n - 1$ n - 1. You need to process $m (1 \leq m \leq 1 0^{7})$ m~(1 \le m \le 10^7) queries asking for the Lowest Common Ancestor (LCA) of pairs of vertices.

The queries are generated as follows. The values $a_{1}, a_{2}$ a_1, a_2 and integers $x, y, z$ x, y, z are given. For $i \geq 3$ i \ge 3, the values $a_{i}$ a_i are computed by the formula:

a_{i} = (x \cdot a_{i - 2} + y \cdot a_{i - 1} + z) mod n .

a_i = (x \cdot a_{i-2} + y \cdot a_{i-1} + z) \bmod n.

The first query is $(a_{1}, a_{2})$ (a_1, a_2). Let the answer to the $(i - 1)$ (i-1)-th query be $v$ . Then the $i$ -th query is defined as

((a_{2 i - 1} + v) mod n, a_{2 i})

((a_{2i-1} + v) \bmod n,\ a_{2i})

Input

The first line contains two integers $n$ and $m$ . The root of the tree is vertex $0$ .

The second line contains $n - 1$ n - 1 integers: the $i$ -th of them is the parent of vertex $i (1 \leq i \leq n - 1)$ i~(1 \le i \le n - 1).

The third line contains two integers $a_{1}$ a_1 and $a_{2} (0 \leq a_{1}, a_{2} < n)$ a_2~(0 \le a_1, a_2 < n).

The fourth line contains three integers $x, y$ and $z (0 \leq x, y, z \leq 1 0^{9})$ z~(0 \le x, y, z \le 10^9).

Output

Print the sum of the vertices that are answers to all queries.

Examples

Example 1

Loading

Example 2

Loading

n (1 \leq n \leq 1 0^{5})

n - 1

m (1 \leq m \leq 1 0^{7})

a_{1}, a_{2}

x, y, z

i \geq 3

a_{i}

a_{i} = (x \cdot a_{i - 2} + y \cdot a_{i - 1} + z) mod n .

(a_{1}, a_{2})

(i - 1)

((a_{2 i - 1} + v) mod n, a_{2 i})

n - 1

i (1 \leq i \leq n - 1)

a_{1}

a_{2} (0 \leq a_{1}, a_{2} < n)

z (0 \leq x, y, z \leq 1 0^{9})