Hashing

curly_braces Criterion 2021 Round 14
Limits 1s, 512 MB

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

For any undirected graph GG with nn vertices and mm edges, where each vertex has a secret value XiX_i, he takes all possible non-empty subsets from the vertex set of GG(There will be 2n12^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 GG.

The MiniHash function takes a subset of vertices of graph GG 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 GG, then the MiniHash function malfunctions and returns 00 instead of the expected MiniHash value. We call two vertices of graph GG to be connected if one vertex is reachable from the other one using one or more edges.

You will be given the graph GG. Initially, it has nn vertices with no edges (all vertices are isolated). You have to answer qq different queries. Each query consists of two integers uu and vv(1u,vn,uv1 \leq u,v \leq n, u \neq v). For each query, you have to add a new edge between node uu and vv, 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(1T105)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(2n106)n ( 2 \leq n \leq 10^6) and q(1q106)q (1 \leq q \leq10^6) — the number of vertices and the number of queries, respectively.

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

The next qq lines each will contain two integers ui(1uin)u_i (1\leq u_i\leq n)and vi(1vin;uivi)v_i (1 \leq v_i \leq n; u_i \neq v_i)uu and vv for the ii’th query.

The sum of nn in all test cases will not exceed 10610^6.

The sum of qq in all test cases will not exceed 10610^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

InputOutput
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

After the final query for the first test case, the subsets are: {1}, {2}, {3},{1,2},{2,3},{1,3} and {1,2,3}. The MiniHash values will be [1, 2, 4, 0, 0, 0, 0] and the hash value will be 7.

After the final query for the second test case, the nonzero MiniHash values will be [1, 2, 4, 8, 5, 9, 6, 10] and the hash value will be 15.


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

For example, if we have two given patterns XX and YY. XX consists of a 3-length bit pattern 101101 and YY also has a 3-length bit pattern 001001. So the resulting bit pattern will be:

101XOR001=100101 XOR 001 = 100

Any integers can be converted into a bit pattern by converting them in base 22. 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=101X=101 represents integer 55 in binary form. For, Y=001Y=001, integer 11 is represented in a 33-bit pattern by appending additional zeros at the leading positions.

Submit

Login to submit.

Statistics

100% Solution Ratio
BigBagEarliest, 7M ago
alifcsejuFastest, 0.2s
aropanLightest, 19 MB
IztihadMustakiShortest, 1386B
Toph uses cookies. By continuing you agree to our Cookie Policy.