LCA Problem Revisited (Easy)
LCA Problem Revisited (Easy)
Given the hanging tree with n (1 ≤ n ≤ 100) vertices, numbered from 0 to n - 1. You need to answer m (1 ≤ m ≤ 100) queries about the least common ancestor for the given pair of vertices.
The queries are generated next way. Given the numbers a1
, a2
and numbers x, y and z. The numbers a3
, ..., a2m
are generated next way: ai
= (x · ai-2
+ y · ai-1
+ z) mod n. The 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
The first line contains two integers n and m. The root of the tree has number 0. The second line contains n - 1 integers, the i-th of which equals to the parent number of vertex i. The third line contains two integers in the range from 0 to n - 1: a1
and a2
. The fourth line contains three integers x, y and z, these numbers are nonnegative and do not exceed 109
.
Output
Print the sum of vertex numbers - the answers to the queries.
3 2 0 1 2 1 1 1 0
2