问题 D: A+B Problem

本题有 $T$ 组数据。对于一组数据，有 $q$ 组询问，每次询问给定两个非负整数 $a,b$，输出 (a+b)mod232(a+b)mod232。

你需要“离线”回答每组询问。具体地，记第 $i$ 次回答的答案为 ansiansi，在第 $i$ 组询问中你读入 ai′,bi′ai′,bi′ 后，真正询问的值为 ai=ai′ xor ansi−1ai=ai′ xor ansi−1，bi=bi′ xor ansi−1bi=bi′ xor ansi−1。特殊地，记 ans0=ansqans0=ansq。

请求出 ans1,...,ansqans1,...,ansq 并输出。如果存在多组解，请输出字典序最小的解。

对于两个长度为 $q$ 的序列 Q1,Q2Q1,Q2，称 Q1Q1 字典序小于 Q2Q2 当且仅当存在 $i\in [1,q]$ 满足以下两个条件:

• ∀1≤j<i，Q1,j=Q2,j∀1≤j<i，Q1,j=Q2,j；
• Q1,i<Q2,iQ1,i<Q2,i。

本题有多组数据。第一行一个正整数 $T$（1≤T≤2×1041≤T≤2×104），表示测试数据组数。

对于每组数据，第一行一个正整数 $q$（1≤q≤3×1051≤q≤3×105）。

接下来 $q$ 行，第 $i$ 行两个非负整数 ai′,bi′ai′,bi′（0≤ai′,bi′≤232−10≤ai′,bi′≤232−1）。

数据保证 ∑q≤3×105∑q≤3×105，保证有解。