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.

N/A

N/A

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.