LCA - 2
LCA - 2
The hanging tree with n (1 ≤ n ≤ 105
) vertices numbered from 0 to n - 1 is given. Answer m (1 ≤ m ≤ 107
) queries about Least Common Ancestor for pair of vertices.
The queries are numbered in the next way. Given values a1
, a2
and x, y и z. Numbers a3
, ..., a2m
are generated in the next way:
ai
= (x * ai-2
+ y * ai-1
+ z) mod n.
First query has the form <a1
, a2
>. If the answer to the (i - 1)-th query is v, then the i-th query has the form <(a2i-1
+ v) mod n, a2i
>.
Input
First line contains two numbers n and m. The root of the tree has number 0. Second line contains n - 1 integers, i-th of these numbers equals to the parent of the vertex i. Third line contains two integers in the range from 0 to n - 1: a1
and a2
. Fourth line contains three integers: x, y and z, they are non-negative and no more than 109
.
Output
Print the sum of the vertex numbers - the answers to all queries.
3 2 0 1 2 1 1 1 0
2
1 2 0 0 1 1 1
0