Problem - 6823

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:

1. If $x \in S(a)$ satisfying $f(x)=0$, then $\exists y \in S(a)$, satisfying $f(y)=x$.

2. If $x,y \in S(a)$ satisfying $f(x)=y$, then $f(y)=0$.

3. $\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.

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$.

Function