Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 4086
Little Sub and a Game

Time Limit: 2 Seconds      Memory Limit: 65536 KB

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?

Input

There 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.

Output

For each test case, you should output a single integer in a line as your answer.

Sample Input

2
1 1
6 3
4 1
2 2
1 3
4 6
5 4
2 2

Sample Output

2
2

Note

In 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
Submit    Status