Problem Statement

You are given a positive integer $N$, a positive integer $X$, and a permutation $P=(P_1,P_2,\ldots,P_N)$ of $(1,2,\ldots,N)$. Only $X$ is given in binary, while $N$ and the elements of $P$ are given in decimal.

Determine whether there exist sequences of non-negative integers $A=(A_1,A_2,\ldots,A_N)$ and $B=(B_1,B_2,\ldots,B_N)$ satisfying all of the following conditions.

• Both $A$ and $B$ are strictly increasing sequences.
• $A_{P_i}=B_i \oplus X$ holds for $i=1,2,\ldots,N$.

Here, the binary operator $\oplus$ denotes the bitwise XOR of non-negative integers.

You are given $T$ test cases; solve each of them.

Constraints

• $1\le T\le 10^5$
• $2\le N\le 2\times 10^5$
• $1\le X < 2^{10^6}$
• $P$ is a permutation of $(1,2,\ldots,N)$.
• The sum of $N$ over all test cases is at most $2\times 10^5$.
• The sum of the number of digits of $X$ in binary over all test cases is at most $10^6$.
• $T,N,P_i$ are given in decimal.
• $X$ is given in binary without leading zeros.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

Each test case is given in the following format:

N
X
P_1 P_2 \ldots P_N

Output

Output the answers for the test cases in order, separated by newlines.

For each test case, output Yes if there exist $A$ and $B$ satisfying all the conditions, and No otherwise.