Function

Problem Description

Given a sequence of length $n$ $a[1..n]$, $S(a)$ is a set generated by $a$:

1. $S(a)=\{a_i|i\in [1,n]\}$, initially.
2. If $x,y \in S(a)$ and $x \oplus y \notin S$, add $x \oplus y$ to $S$. Note that here $\oplus$ denotes the bitwise exclusive or, i.e. , $xor$. If you knew little about that, please refer to https://en.wikipedia.org/wiki/Exclusive. Construct a mapping $f:S(a) \rightarrow S(a)$ that satisfies all the following conditions:
3. If $x \in S(a)$ satisfying $f(x)=0$, then $\exists y \in S(a)$, satisfying $f(y)=x$.
4. If $x,y \in S(a)$ satisfying $f(x)=y$, then $f(y)=0$.
5. $\forall x,y \in S(a), \ f(x\oplus y)=f(x) \oplus f(y)$. This problem contains two modes, specified by a parameter $op$. The first mode: The parameter $op=construct$, it means that you are a contestant and you need to construct a solution, which will be checked by $special \ judge$ on the evaluation machine. Firstly, print $NoSolution$ if there doesn't exist a mapping function $f$ on $S(a)$ satisfying the above conditions and go on next test case( but you should also read some following extra data and do not print anything, see input ), otherwise print $HaveSolution$ representing that you have a solution. To check whether your solution is correct, then you are given an integer $m$ denoting the number of queries you should answer. For $i$-th query, read a nonnegative integer $x_i$, print $f(x_i)$ if $x_i \in S(a)$ or $-1$ if $x_i \notin S(a)$. If there exists a solution $g$ satisfying $g(x_i)=f(x_i),i\in [1,m]$, your solution will be assumed to be correct, otherwise it is wrong. The second mode: The parameter $op=check$, it means that you are the evaluation machine and you need to check a solution. Firstly, read a string $st$, $st=HaveSolution$ or $st=NoSolution$ denoting whether the evaluation machine assumes that there is a solution. If the conclusion is wrong, print $No$ and go on next test case(\textbf{but maybe you should also read some following extra data and do not print anything, see input}). Otherwise, if $st=HaveSolution$, you should check whether the construction $f$ is correct. You are given an integer $m$ and $m$ pieces of information. For one of them, you should read a nonnegative integer $x_i$, and $f(x_i)$ is either a nonnegative integer or $-1$ according to whether the evaluation machine assumes that $x_i \in S(a)$. $-1$ means that it assumes that $x_i \notin S(a)$. And you should also check that $-1$ is correct or not. Namely, you have to note that if the given $x_i \notin S(a)$, but $f(x_i) \ne -1$, it is a wrong construction. Note that the solution given by the evaluation machine may be not generated randomly. If there exists a solution $g$ satisfying $g(x_i)=f(x_i),i\in [1,m]$, you should print $Yes$ denoting that the solution is correct, otherwise it is wrong and you should print $No$. That is to say, the criterion is the same for the two modes. See the example for details.

Input

The first line contains one integer $T$, $T \in [1,550]$. For each test case: The first line contains one integer $n$, $n \in [1,10^6]$. The second line contains $n$ integers $a_1,a_2,\cdots,a_n$, $a_i \in [0,2^{60})$. Then you should read a string $op$. If $op=contruct$, next line contains one integer $m$. The $i$-th of the next $m$ lines contains one integer $x_i$, $x_i \in [0,2^{60})$. If $op=check$, then next line contains a string $st$, $st=HaveSolution$ or $st=NoSolution$. If $st=HaveSolution$, the next line contains one integer $m$. Each of the next $m$ lines contains $2$ integers $x_i$ and $f(x_i)$, $x_i \in [0,2^{60}),f(x_i) \in [-1,2^{60})$. The total of $n$ does not exceed $2 \times 10^6$. The total of $m$ does not exceed $2 \times 10^5$.

Output

For each test case: If $op=construct$, print $HaveSolution$ if you have a solution and for each $x_i$, output a line containing $f(x_i)$, or print $NoSolution$ with no extra output if you assumes that there doesn't exist a solution. If $op=check$, output a line containing $Yes$ if it is correct, otherwise print $No$.

Sample Input

4
4
1 1 2 3
check
HaveSolution
4
1 0
2 1
3 1
4 -1
1
1
construct
1
1
3
1 2 3
check
HaveSolution
2
1 0
4 1
3
1 2 3
construct
2
1
4

Sample Output

Yes
NoSolution
No
HaveSolution
3
-1

Source

2020 Multi-University Training Contest 5