Shreas has created a new revolutionary hashing function that calculates hash values of graphs.
For any undirected graph with vertices and edges, where each vertex has a secret value , he takes all possible non-empty subsets from the vertex set of (There will be 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 .
The MiniHash function takes a subset of vertices of graph 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 , then the MiniHash function malfunctions and returns instead of the expected MiniHash value. We call two vertices of graph to be connected if one vertex is reachable from the other one using one or more edges.
You will be given the graph . Initially, it has vertices with no edges (all vertices are isolated). You have to answer different queries. Each query consists of two integers and (). For each query, you have to add a new edge between node and , 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.
The input will start with an integer — the number of test cases.
Each test case will start with a line containing two positive integers and — the number of vertices and the number of queries, respectively.
The next line will contain space-separated integers — the secret values.
The next lines each will contain two integers and — and for the ’th query.
The sum of in all test cases will not exceed .
The sum of in all test cases will not exceed .
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.
Input | Output |
---|---|
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 or . The XOR operation results in a single bit pattern, the length of which is equal to the length of the two given patterns. The position of the resulting bit pattern is computed from the position of both the given patterns. The resulting value of position i is , if just one of the values of the given patterns in that position is . Otherwise, the resulting value is 0.
For example, if we have two given patterns and . consists of a 3-length bit pattern and also has a 3-length bit pattern . So the resulting bit pattern will be:
Any integers can be converted into a bit pattern by converting them in base . Any set of integers can be converted into bit patterns of the same length, possibly by adding some leading zeros. In the above example, represents integer in binary form. For, , integer is represented in a -bit pattern by appending additional zeros at the leading positions.