7490: Function

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

1. S(a)={ai|i∈[1,n]}, initially.

2. If x,y∈S(a) and x⊕y∉S, add x⊕y to S.

Note that here ⊕ 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)→S(a) that satisfies all the following conditions:

1. If x∈S(a) satisfying f(x)=0, then ∃y∈S(a), satisfying f(y)=x.

2. If x,y∈S(a) satisfying f(x)=y, then f(y)=0.

3. ∀x,y∈S(a), f(x⊕y)=f(x)⊕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 xi, print f(xi) if xi∈S(a) or −1 if xi∉S(a).

If there exists a solution g satisfying g(xi)=f(xi),i∈[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 xi, and f(xi) is either a nonnegative integer or −1 according to whether the evaluation machine assumes that xi∈S(a). −1 means that it assumes that xi∉S(a). And you should also check that −1 is correct or not. Namely, you have to note that if the given xi∉S(a), but f(xi)≠−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(xi)=f(xi),i∈[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∈[1,550].

For each test case:

The first line contains one integer n, n∈[1,106].

The second line contains n integers a1,a2,⋯,an, ai∈[0,260).

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 xi, xi∈[0,260).

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 xi and f(xi), xi∈[0,260),f(xi)∈[−1,260).

The total of n does not exceed 2×106.
The total of m does not exceed 2×105.
 

For each test case:

If op=construct, print HaveSolution if you have a solution and for each xi, output a line containing f(xi), 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.

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

Yes
NoSolution
No
HaveSolution
3
-1