favorite We need a little bit of your help to keep things running, click on this banner to learn more

ADA University - February 12 - LCA

LCA Problem Revisited (Easy)

Given the hanging tree with n (1n100) vertices, numbered from 0 to n - 1. You need to answer m (1m100) 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>.


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.


Print the sum of vertex numbers - the answers to the queries.

Time limit 1 second
Memory limit 64 MiB
Input example #1
3 2
0 1
2 1
1 1 0
Output example #1