Tree queries#236
You are given a connected graph with vertexes and n-1 edges. In other words, you are given a tree. Vertex is the root of the tree. In vertex there is an integer a_v written on it. Let's define cost of the tree as XOR sum of all its values. You were given queries, containing two integers and . Each query makes a_u = a_u \oplus x, where belongs to the subtree of the vertex and denotes XOR operation. As we all know, this problem can be easily solved by our participants, but if all was that easy, this problem wouldn't appear at this Olympiad. You know that some queries were changed by angry Anton. Thus, you are asked to find the sum of costs modulo , of all 2^q trees that can be obtained by applying some (possibly none) queries on the tree.
The first line of input contains two integers (1 \le n \le 2 \cdot 10^5) and (1 \le q \le 2 \cdot 10^5) — number of vertexes in the tree and number of queries accordingly.
The second line of input contains integers a_i (0 \le a_i < 2^{60}) — values written on the vertex of the tree.
The following n-1 lines contain two integers and each — edges of the given tree.
The following lines contain two integers (1 \le v \le n) and (0 \le x < 2^{60}) each — description of queries.
Print one integer in the first line — answer to the problem.
Example 1
( points): q \le 2;
( points): q \le 10;
( points): q \le 20;
( points): a_i, x < 2;
( points): a_i, x < 1024;
( points): a_i, x < 2^{18};
( points): no additional restrictions.