题目内容

猫猫虫们喜欢在别人的身上睡觉。从左到右有无限多个可以堆猫猫虫的位置（我们称为"堆"）。接下来会依次走来 $n$ 只猫猫虫，第 $i$ 只猫猫虫的大小为 $a_i$。放置规则如下：

• 从第一个堆开始向右依次检查；
• 如果当前堆为空，或者该堆最上面的猫猫虫大小 $>$ 当前猫猫虫大小，则把当前猫猫虫放到这个堆的最上面；否则继续检查下一个堆；
• 如果一路检查到某个空堆，那么就在该空堆新建一个堆并把当前猫猫虫放上去。

在每次放置完一只猫猫虫后，记每个堆的高度（即堆中猫猫虫的只数），请你输出当前所有堆的高度的异或和（即所有高度按位异或的结果）。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T$ ($1 \le T \le 2 \times 10^5$) 表示数据组数，每组测试数据描述如下：

• 第一行输入一个整数 $n$ ($1 \le n \le 4 \times 10^5$) 表示猫猫虫的数量。
• 第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n$ ($1 \le a_i \le 10^9$) 表示每只猫猫虫的大小。 除此之外，保证单个测试文件的 $n$ 之和不超过 $4 \times 10^5$。

输出描述

对于每一组测试数据，新起一行。输出 $n$ 个整数（以空格隔开），其中第 $i$ 个数表示放置完前 $i$ 只猫猫虫后，所有堆的高度的异或和。

样例1

输入

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

输出

1 0 3 0 1
1 0 1 0

说明

• 对于第一组数据 $n=5$，$a = \{3,3,2,2,1\}$，每次放置后的堆高度序列依次可能为 $\{1\}$、$\{1,1\}$、$\{2,1\}$、$\{2,2\}$、$\{3,2\}$，对应的异或和依次为 $1$、$0$、$3$、$0$、$1$，与输出一致。
• 对于第二组数据 $a = \{1,2,3,4\}$，每次都会新建一个堆，堆高度序列依次为 $\{1\}$、$\{1,1\}$、$\{1,1,1\}$、$\{1,1,1,1\}$，异或和依次为 $1$、$0$、$1$、$0$。