
ZOJ Problem Set  4086
Little Sub has another friend called lqybzx. One day, they are playing an interesting game. In this game, there is a variable called "Justic Oops Heltion Attacks Neets Number" which is written as "JOHANN". Initially, JOHANN is equal to $0$. $N$ pairs of numbers ($x_i,y_i$) are given to Little Sub while $M$ pairs ($x'_i,y'_i$) are given to lqybzx. Firstly, for every pair ($x_i,y_i$), Little Sub will choose either $x_i$ or $y_i$. Suppose he choose $k$, JOHANN will be changed to (JOHANN $\oplus \ k$). ($\oplus$ denotes bitwise exclusive or) After Little Sub's $N$ operations, lqybzx will do the same with his $M$ pairs. They know about each other's pairs from the beginning. Little Sub wishes the final value of JOHANN to be as great as possible while lqybzx wishes it to be as small as possible. Little Sub and lqybzx are very clever boys and they will choose the best strategy. Can you predict the final value of JOHANN? InputThere are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 20$), indicating the number of test cases. For each test case: The first line contains two integers $N$ and $M$ ($1 \leq N,M \leq 10000$). Then $N$ lines follow. In each line, there are two integers $x_i,y_i$ ($1 \leq x_i,y_i \leq 10^{18}$), representing Little Sub's pairs. Then $M$ lines follow. In each line, there are two integers $x'_i,y'_i$ ($1 \leq x'_i,y'_i \leq 10^{18}$), representing lqybzx's pairs. OutputFor each test case, you should output a single integer in a line as your answer. Sample Input2 1 1 6 3 4 1 2 2 1 3 4 6 5 4 2 2 Sample Output2 2 NoteIn the first sample, if Little Sub chooses $6$, lqybzx will choose $4$ and the result will be $2$. If Little Sub chooses $3$, lqybzx will choose $1$ and the result will also be $2$. Therefore the answer is $2$. Author: ZHENG, Honghu Source: ZOJ Monthly, January 2019 