A+B Problem

Problem Description

本题有 $T$ 组数据。对于一组数据，有 $q$ 组询问，每次询问给定两个非负整数 $a,b$，输出 $(a+b)\bmod 2^{32}$。 你需要“离线”回答每组询问。具体地，记第 $i$ 次回答的答案为 $ans_i$，在第 $i$ 组询问中你读入 $a_i',b_i'$ 后，真正询问的值为 $a_i=a_i'\text{ xor }ans_{i-1}$，$b_i=b_i'\text{ xor }ans_{i-1}$。特殊地，记 $ans_0=ans_q$。 请求出 $ans_1,...,ans_q$ 并输出。如果存在多组解，请输出字典序最小的解。 对于两个长度为 $q$ 的序列 $Q_1,Q_2$，称 $Q_1$ 字典序小于 $Q_2$ 当且仅当存在 $i \in [1, q]$ 满足以下两个条件：

• $\forall 1 \le j < i，Q_{1,j} = Q_{2,j}$；
• $Q_{1,i} < Q_{2,i}$。

Input

本题有多组数据。第一行一个正整数 $T$（$1\le T\le 2\times 10^4$），表示测试数据组数。 对于每组数据，第一行一个正整数 $q$（$1\le q\le 3\times 10^5$）。 接下来 $q$ 行，第 $i$ 行两个非负整数 $a'_i,b'_i$（$0\le a'_i,b'_i\le 2^{32}-1$）。 数据保证 $\sum q\le 3\times 10^5$，保证有解。

Output

对于一组数据，输出 $q$ 行，第 $i$ 行表示第 $i$ 组询问的答案 $ans_i$。

Sample Input

2
2
0 1
1 0
3
3 2
0 0
3 0

Sample Output

1
1
1
2
3

Source

2024“钉耙编程”中国大学生算法设计超级联赛（10）