Bitwise swaps


Submit solution


Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

Given a sequence \(a\) consisting of \(n\) integers \(a_1,a_2,…,a_n\), check if you can make this sequence sorted using the following operation :

Pick a pair of indices \((i,j)\) with \(i \neq j\) and \(a_i \& a_j \neq 0\) then swap the values of \(a_i\) and \(a_j\) (\(\&\) is bitwise and).

Input Specification

The first line contains the number of test cases \(t\) \((1\leq t \leq 10^4)\). Description of the test cases follows. The first line of each test case contains a single integer \(n\) \((1\leq n \leq 3.10^5)\) The second line of each test case contains n integers \(a_1,a_2,…,a_n\) \((0 \leq a_i \leq 2^{31}-1)\)

Output Specification

For each test case, print Yes if you can sort the array using the operations described in the statement and No otherwise (case sensitive).

Sample Input

4
3
6 4 2
6
9 34 4 24 1 6
6
9 34 24 4 1 6
2
1 0

Sample Output

Yes
Yes
No
No

Scoring

\begin{array}{|c|c|c|} \hline \text{Group} & \text{Points} & \text{Constraints} \cr \hline 1 & 10 & 0 \leq a_i \leq 1 \cr \hline 2 & 25 & 0 \leq n \leq 3000 \cr \hline 3 & 55 & \text{ No additional constraints } \cr \hline \end{array}


Comments

There are no comments at the moment.