CF1765G.Guess the String

This is an interactive problem. You have to use flush operation right after printing each line. For example, in C++ you should use the function fflush(stdout), in Java or Kotlin — System.out.flush(), and in Python — sys.stdout.flush().

The jury has a string $s$ consisting of characters 0 and/or 1. The first character of this string is 0. The length of this string is $n$. You have to guess this string. Let's denote $s[l..r]$ as the substring of $s$ from $l$ to $r$ (i. e. $s[l..r]$ is the string $s_ls_{l+1} \dots s_r$).

Let the prefix function of the string $s$ be an array $[p_1, p_2, \dots, p_n]$, where $p_i$ is the greatest integer $j \in [0, i-1]$ such that $s[1..j] = s[i-j+1..i]$. Also, let the antiprefix function of the string $s$ be an array $[q_1, q_2, \dots, q_n]$, where $q_i$ is the greatest integer $j \in [0, i-1]$ such that $s[1..j]$ differs from $s[i-j+1..i]$ in every position.

For example, for the string 011001, its prefix function is $[0, 0, 0, 1, 1, 2]$, and its antiprefix function is $[0, 1, 1, 2, 3, 4]$.

You can ask queries of two types to guess the string $s$:

• $1$ $i$ — "what is the value of $p_i$?";
• $2$ $i$ — "what is the value of $q_i$?".

You have to guess the string by asking no more than $789$ queries. Note that giving the answer does not count as a query.

In every test and in every test case, the string $s$ is fixed beforehand.

Interaction

Initially, the jury program sends one integer $t$ ($1 \le t \le 100$) — the number of test cases.

At the start of each test case, the jury program sends one integer $n$ ($2 \le n \le 1000$) — the length of the string.

After that, your program can submit queries to the jury program by printing one of the following lines (do not forget to flush the output after printing a line!):

• $1$ $i$ — the query "what is the value of $p_i$?";
• $2$ $i$ — the query "what is the value of $q_i$?".

For every query, the jury prints one integer on a separate line. It is either:

• the answer for your query, if the query is correct and you haven't exceeded the query limit;
• or the integer $-1$, if your query is incorrect (for example, the constraint $1 \le i \le n$ is not met) or if you have asked too many queries while processing the current test case.

To submit the answer, your program should send a line in the following format (do not forget to flush the output after printing a line!):

• $0$ $s$, where $s$ is a sequence of $n$ characters 0 and/or 1.

If your guess is correct, the jury program will print one integer $1$ on a separate line, indicating that you may proceed to the next test case (or terminate the program, if it was the last test case) and that the number of queries you have asked is reset. If it is not correct, the jury program will print one integer $-1$ on a separate line.

After your program receives $-1$ as the answer, it should immediately terminate. This will lead to your submission receiving the verdict "Wrong Answer". If your program does not terminate, the verdict of your submission is undefined.

这是一个交互式问题。每次输出一行后，你必须立即执行刷新操作。例如，在 C++ 中应使用函数 fflush(stdout)，在 Java 或 Kotlin 中应使用 System.out.flush()，在 Python 中应使用 sys.stdout.flush()。

评测系统有一个由字符 0 和/或 1 构成的字符串 $s$。该字符串的第一个字符是 0，长度为 $n$。你需要猜出这个字符串。记 $s[l..r]$ 为 $s$ 中从位置 $l$ 到 $r$ 的子串（即 $s[l..r]$ 表示字符串 $s_ls_{l+1} \dots s_r$）。

定义字符串 $s$ 的前缀函数为数组 $[p_1, p_2, \dots, p_n]$，其中 $p_i$ 是满足 $s[1..j] = s[i-j+1..i]$ 的最大整数 $j \in [0, i-1]$。
同时，定义字符串 $s$ 的反前缀函数为数组 $[q_1, q_2, \dots, q_n]$，其中 $q_i$ 是满足 $s[1..j]$ 与 $s[i-j+1..i]$ 在每一位上均不同的最大整数 $j \in [0, i-1]$。

例如，对于字符串 011001，其前缀函数为 $[0, 0, 0, 1, 1, 2]$，其反前缀函数为 $[0, 1, 1, 2, 3, 4]$。

你可以通过以下两种类型的查询来猜测字符串 $s$：

• 1 i —— “$p_i$ 的值是多少？”；
• 2 i —— “$q_i$ 的值是多少？”。

你必须在不超过 $789$ 次查询内猜出该字符串。（注意：提交答案本身不计入查询次数。）

在每个测试点及每个测试用例中，字符串 $s$ 均预先固定。

交互流程

初始时，评测程序会先向你的程序发送一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。

每个测试用例开始时，评测程序会发送一个整数 $n$（$2 \le n \le 1000$），表示字符串的长度。

此后，你的程序可通过输出以下格式之一的行向评测程序发起查询（注意：每输出一行后务必刷新输出！）：

• 1 i —— 查询“$p_i$ 的值是多少？”；
• 2 i —— 查询“$q_i$ 的值是多少？”。

对每个查询，评测程序将在单独一行输出一个整数，该整数为：

• 你所提查询的正确答案（若查询合法且尚未超出查询次数限制）；
• 或整数 $-1$（若查询非法（例如不满足 $1 \le i \le n$）或当前测试用例中已超出查询次数限制）。

要提交最终答案，你的程序应输出如下格式的一行（注意：输出后务必刷新输出！）：

• 0 s，其中 $s$ 是一个长度为 $n$、仅含字符 0 和/或 1 的字符串。

若你的答案正确，评测程序将在单独一行输出整数 $1$，表示你可以进入下一个测试用例（若这是最后一个测试用例，则可终止程序），并且查询次数将被重置。若答案错误，评测程序将在单独一行输出整数 $-1$。

一旦你的程序收到答案 $-1$，应立即终止。这将导致你的提交获得 “Wrong Answer” 判定。若你的程序未及时终止，则提交结果未定义。

The example contains one possible way of interaction in a test where $t = 2$, and the strings guessed by the jury are 011001 and 00111. Note that everything after the // sign is a comment that explains which line means what in the interaction. The jury program won't print these comments in the actual problem, and you shouldn't print them. The empty lines are also added for your convenience, the jury program won't print them, and your solution should not print any empty lines.

该示例展示了一种在 $t = 2$ 的测试中可能的交互方式，评测程序所选定的字符串分别为 011001 和 00111。注意：// 符号之后的所有内容均为注释，用于说明交互中各行的含义。在实际题目中，评测程序不会输出这些注释，你也不应输出它们。空行同样仅为方便阅读而添加；评测程序不会输出空行，你的程序也不应输出任何空行。