Tree queries

You are given a connected graph with $n$ vertexes and $n-1$ edges. In other words, you are given a tree. Vertex $1$ is the root of the tree. In vertex $v$ 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 $q$ queries, containing two integers $v$ and $x$. Each query makes $a_u$ = $a_u\oplus x$, where $u$ belongs to the subtree of the vertex $v$ and $\oplus$ 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 $998244353$, of all $2^q$ trees that can be obtained by applying some (possibly none) queries on the tree.

Input

The first line of input contains two integers $n$ ($1\le n\le 2\cdot 10^5$) and $q$ ($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 $n$ 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 $u$ and $v$ each — edges of the given tree.

The following $q$ lines contain two integers $v$ ($1\le v\le n$) and $x$ ($0\le x<2^{60}$) each — description of queries.

Output

Print one integer in the first line — answer to the problem.

Examples

Scoring

1. ($7$ points): $q\le 2$;

2. ($12$ points): $q\le 10$;

3. ($16$ points): $q\le 20$;

4. ($18$ points): $a_i,x<2$;

5. ($13$ points): $a_i,x<1024$;

6. ($15$ points): $a_i,x<2^{18}$;

7. ($19$ points): no additional restrictions.