Tree LCA 3

Problem Description

You are given a tree rooted at node $1$.

You must answer $m$ queries. In each query you are given two distinct numbers $x, y$ ($x \neq y$), and you must output the lowest common ancestor (LCA) of $x$ and $y$.

Input Format

The first line contains five integers $n, m, A, B, C$ ($0 \leq A, B, C \leq 2^{32} - 1$).

The next $n - 1$ lines each contain two integers $x, y$ ($x \neq y$), denoting an edge between $x$ and $y$.

To avoid excessively large input, the queries are generated by the following code:

unsigned int A, B, C;
inline unsigned int rng61() {
    A ^= A << 16;
    A ^= A >> 5;
    A ^= A << 1;
    unsigned int t = A;
    A = B;
    B = C;
    C ^= t ^ A;
    return C;
}
int main(){
    scanf("%d%d%u%u%u", &n, &m, &A, &B, &C);
    // input the tree edges
    for (int i = 1; i <= m; i++) {
        unsigned int u = rng61() % n + 1, v = rng61() % n + 1;
        ans[i] = LCA(u, v);
    }
}

(That is, you do not read the queries explicitly; they are produced internally by this generator.)

Output Format

Suppose the answer to the $i$-th query is $ans_i$. Output the XOR sum of $ans_i \times i$ over all queries, i.e. $ans_1 \times 1 \oplus ans_2 \times 2 \oplus \dots \oplus ans_m \times m$.

Sample Input

5 5 1 2 3
1 2
1 3
3 4
3 5

Sample Output

9

Constraints

• $1 \leq n \leq 5 \times 10^5$
• $1 \leq x, y \leq n,\ x \neq y$
• $m \leq 10^7$