Hashing

Shreas has created a new revolutionary hashing function that calculates hash values of graphs.

For any undirected graph $G$ with $n$ vertices and $m$ edges, where each vertex has a secret value $X_i$, he takes all possible non-empty subsets from the vertex set of $G$(There will be $2^n-1$ subsets). Then he calculates MiniHash values for each of the subsets using his custom MiniHash function. He calls the XOR of all those MiniHash values to be the hash value of Graph $G$.

The MiniHash function takes a subset of vertices of graph $G$ and returns the XOR of the secret values of all the vertices in that subset. But his custom MiniHash function has a bug, if two vertices in a subset are connected in graph $G$, then the MiniHash function malfunctions and returns $0$ instead of the expected MiniHash value. We call two vertices of graph $G$ to be connected if one vertex is reachable from the other one using one or more edges.

You will be given the graph $G$. Initially, it has $n$ vertices with no edges (all vertices are isolated). You have to answer $q$ different queries. Each query consists of two integers $u$ and $v$($1 \leq u,v \leq n, u \neq v$). For each query, you have to add a new edge between node $u$ and $v$, and print the hash value of the current graph. All updates are permanent, meaning if you add an edge to the graph in a query, it stays on the graph for all the queries after that.

Input

The input will start with an integer $T ( 1 \leq T \leq 10^5)$ — the number of test cases.

Each test case will start with a line containing two positive integers $n ( 2 \leq n \leq 10^6)$ and $q (1 \leq q \leq10^6)$ — the number of vertices and the number of queries, respectively.

The next line will contain $n$ space-separated integers $X_1, X_2, \dots, X_n (0 \leq X_i \leq 10^{18})$ — the secret values.

The next $q$ lines each will contain two integers $u_i (1\leq u_i\leq n)$and $v_i (1 \leq v_i \leq n; u_i \neq v_i)$— $u$ and $v$ for the $i$’th query.

The sum of $n$ in all test cases will not exceed $10^6$.

The sum of $q$ in all test cases will not exceed $10^6$.

Output

For each test case, print the case number and for each query, print the hash value the function will generate for the current graph after processing the query in a new line.

Sample

2
3 2
1 2 4
1 2
1 3
4 2
1 2 4 8
1 2
3 4

Case 1:
4
7
Case 2:
0
15

XOR is a bitwise operation that is performed on two bit patterns of equal length. Bit patterns are strings that only contain $0$ or $1$. The XOR operation results in a single bit pattern, the length of which is equal to the length of the two given patterns. The $i-th$ position of the resulting bit pattern is computed from the $i-th$ position of both the given patterns. The resulting value of position i is $1$, if just one of the values of the given patterns in that position is $1$. Otherwise, the resulting value is 0.

For example, if we have two given patterns $X$ and $Y$. $X$ consists of a 3-length bit pattern $101$ and $Y$ also has a 3-length bit pattern $001$. So the resulting bit pattern will be:

$101 XOR 001 = 100$

Any integers can be converted into a bit pattern by converting them in base $2$. Any set of integers can be converted into bit patterns of the same length, possibly by adding some leading zeros. In the above example, $X=101$ represents integer $5$ in binary form. For, $Y=001$, integer $1$ is represented in a $3$-bit pattern by appending additional zeros at the leading positions.