This is an interactive problem.

There are $2n$ ($1 \le n \le 10^5$) players, numbered from $1$ to $2n$. Each player is either a Crewmate or an Impostor. Their roles are represented by a hidden binary array $a$: $a_i=0$ means that player $i$ is a Crewmate, and $a_i=1$ means that player $i$ is an Impostor.

It is guaranteed that there are strictly fewer than $n$ Impostors.

In one query, you may arrange all players in any order. If their original identities in that order are $p_1,p_2,\ldots,p_{2n}$, the players are divided into the $n$ pairs

For every pair, you receive the number of Impostors in it. Thus, one query returns all $n$ pair sums simultaneously.

Determine the role of every player using at most two queries per test case. You may choose your second arrangement after reading the response to your first query.

The hidden array is fixed before the interaction for each test case begins and does not change in response to your queries. Player identities always refer to their original numbers, regardless of earlier arrangements.

Interaction

This is an interactive problem with a function interface. You must not implement main. Instead, your solution must #include "amongus.h" and implement the function

std::string solve(int n);

This function is called once for each test case, (but can be called multiple times per process!) with the value $n$ of that test case. It must return the hidden array as a string of exactly $2n$ characters, each of which is 0 or 1, with no spaces between its characters. Its $i$-th character (0-indexed: result[i - 1]) must equal $a_i$, so the answer is in the players' original identity order.

To make a query, call the function

std::vector<int> query(const std::vector<int>& p);

where p has exactly $2n$ elements and is a permutation of the integers from $1$ to $2n$. Note that the values in p are 1-indexed player numbers.

The function returns a vector s of $n$ integers, where

In terms of C++ (0-indexed) vector positions, this means s[j] = a[p[2 * j]] + a[p[2 * j + 1]] for $0 \le j < n$, where a[x] is the state of player $x$.

You may call query at most two times during each call of solve. The query counter is reset at the start of every test case. It is allowed to return the answer after zero, one, or two queries.

Since solve is called several times in a single run of your program, make sure to reset any global variables you use at the start of each call.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

The interactor is not adaptive. This means that the hidden array is fixed before any queries are made for that test case and will not change throughout the interaction.

If p does not have exactly $2n$ elements, is not a permutation of $1, 2, \ldots, 2n$, or if you call query more than two times in the same test case, your program is terminated immediately and you will receive Wrong Answer. You will also receive Wrong Answer if solve returns an incorrect string.

Do not read anything from stdin and do not print anything to stdout!

Sample grader

The sample grader reads the input in the following format:

• line $1$: $t$, the number of test cases;
• then, for each test case, two lines: the integer $n$, followed by a string of $2n$ characters 0/1 describing the hidden array $a$.

For each test case, the sample grader calls solve(n) and prints the returned string on its own line. If an invalid query is made, it prints -1 and terminates. Note that the sample grader does not check whether the returned answer is correct; the official grader does.

Example 1

Input for the sample grader:

2
2
0001
1
00

Interaction:

Output of the sample grader:

0001
00

Note

In the first test case, $n=2$ and the hidden array is 0001, so only player $4$ is an Impostor.

The first query, query({1, 2, 3, 4}), forms the pairs $(1,2)$ and $(3,4)$. The first pair contains no Impostors, and the second pair contains one, so the response is {0, 1}.

The second query, query({1, 3, 2, 4}), forms the pairs $(1,3)$ and $(2,4)$. Their numbers of Impostors are again $0$ and $1$, respectively. The contestant then returns "0001".

In the second test case, $n=1$ and the hidden array is 00. Both players are Crewmates, so the contestant returns "00" without making any queries.