Guess the String

题意翻译

### 题目描述 这是一道交互题。 有一个长度为 $n$ 的 01 串 $s$。第一个字符一定为 $0$，即 $s_1 = 0$（注意本题下标均从 $1$ 开始）。记 $s[l\dots r]$ 为子串 $s_ls_{l+1}\dots s_r$。你需要猜出这个 01 串。 记 $s$ 的前缀函数为 $p$，即 $p_i$ 表示最大的 $j$，满足 $0\le j < i$ 且 $s[1\dots j] = s[i - j + 1\dots i]$。记 $s$ 的反前缀函数为 $q$，即 $q_i$ 表示最大的 $j$，满足 $0\le j < i$ 且 $s[1\dots j] $ 与 $ s[i - j + 1\dots i]$ 的每一位都不相同。 例如当 $s=011001$ 时，$p=[0,0,0,1,1,2]$，$q=[0,1,1,2,3,4]$。 你可以询问两种问题： - 1 $\,i$：表示询问 $p_i$ 的值； - 2 $\,i$：表示询问 $q_i$ 的值。 你需要在 $789$ 次 **询问** 操作内得到答案，即输出 $s$ 并不算在上述操作数限制内。 交互器 **不是自适应的**，即所有测试点的每组测试数据的 $s$ 不会随着评测而改变。 ### 输入/输出格式 开始读入一个整数 $t$（$1\le t\le 100$）表示数据组数，接下来依次读入各组测试数据。对于一组测试数据： 第一行一个整数 $n$（$2\le n\le 1000$）表示 $s$ 的长度。 之后你需要输出你的询问或是输出你猜的串 $s$，格式如下： - 1 $\,i$：表示询问 $p_i$ 的值； - 2 $\,i$：表示询问 $q_i$ 的值； - 0 $\,s$：表示你猜出的串 $s$。 对于每次询问，交互器返回一行一个整数： - 对于前两种询问，当你的询问合法且未超过次数限制时，交互器返回答案；否则返回 $-1$； - 对于第三种询问，若答案正确返回 $1$，否则返回 $0$。 若第三种询问返回了 $1$，表示答案正确，此时你应该进入下一组测试数据（若已经是最后一组测试数据了就结束程序）并且询问次数清零。若交互器返回了 $-1$，不论哪种情况，你都应该立即结束程序，得到 $\texttt{Wrong Answer}$。 样例解释见样例输入/输出，程序不会读入到也不应该输出样例中注释内容与空行

题目描述

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.

输入输出格式

输入格式

输出格式

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.

输入输出样例

输入样例 #1

2 // 2 test cases
6 // n = 6

0 // p[3] = 0

1 // q[2] = 1

4 // q[6] = 4

1 // p[4] = 1

1 // answer is correct
5 // n = 5

1 // p[2] = 1

2 // q[4] = 2

2 // q[5] = 2

1 // answer is correct

输出样例 #1

1 3      // what is p[3]?

2 2      // what is q[2]?

2 6      // what is q[6]?

1 4      // what is p[4]?

0 011001 // the guess is 011001


1 2      // what is p[2]?

2 4      // what is q[4]?

2 5      // what is q[5]?

0 00111  // the guess is 00111

说明

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.