You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

你有一个序列 $a_i$，保证序列中不存在重复数字，你可以执行以下操作任意多次：

• 选择 $i \neq j$，若 $a_i \oplus a_j \neq a_i \mid a_j$，则将 $a_i$ 与 $a_j$ 交换位置，其中 $\oplus$ 表示按位异或。

请判断能否通过若干次操作（包括 $0$ 次）将序列升序排序。

输入格式

输入包含多个测试用例。第一行输入一个正整数 $T\,(T \le 10^5)$， 表示测试用例的数量。

每个测试用例的第一行输入一个正整数，表示序列长度 $n\,(n\leq 10^6, \sum n \le 4\times 10^6)$。

第二行包括 $n$ 个数，表示 $a_1, a_2, \ldots, a_n\,(0\le a_i < 2^{31})$。

输出格式

对每个测试用例，如果能通过若干次操作（包括 $0$ 次）将序列升序排序，输出 $\texttt{Yes}$，否则输出 $\texttt{No}$。

输入输出样例 #1

输入 #1

6
2
1 2
2 
2 1
3
12 6 3
3
3 12 6
4
3 1 2 4
9
9 8 7 6 5 4 3 2 1

输出 #1

Yes
No
Yes
Yes
Yes
Yes

说明/提示

样例解释

在第一组数据中，$a_i$ 已经升序排列，应输出 "Yes" ；

在第二组数据中，因为 $1\oplus2=1\,|\,2$ ，所以 $1,2$ 不能互换，进而不可能升序排序，应输出 "No" ；

在第三组数据中，由互换规则知 $12,6$ 以及 $6,3$ 可以分别互换，但是 $12,3$ 不能互换。该组序列可以通过下面的方法完成升序排序：$[12,6,3]\rightarrow[12,3,6]\rightarrow[6,3,12]\rightarrow[3,6,12]$ ，应输出 "Yes" 。