Decoding the Ancient Stone Tablet

Bitaro and Bibako are archaeologists investigating ancient ruins in the JOI kingdom. They discovered an ancient stone tablet and a mysterious machine. The tablet contains a binary string ( S ) of length ( N ) whose characters are either 0 or 1. The machine works as follows:

1. It initializes an internal memory value to 0.
2. It then performs ( N ) operations. In the ( (i+1))-th operation (( 0 \le i \le N-1 )), let the current memory value be ( x ) and read the character ( S_i ) (the ( i )-th character of ( S ), 0-indexed):
   • If ( S_i = 0 ), it sets the memory to ( a_x ) (the ( x )-th element of sequence ( a )).
   • If ( S_i = 1 ), it sets the memory to ( b_x ) (the ( x )-th element of sequence ( b )).
3. After all operations, the machine outputs the final value of the memory.

To use the machine, you must supply an integer ( m ) and two sequences of integers ( a ) and ( b ) (each of length ( m )), with the following restrictions:

• ( 1 \le m \le 1002 ).
• All elements of ( a ) and ( b ) are between 0 and ( m-1 ) (inclusive).

Bitaro wants to determine the unknown string ( S ) by making at most 1000 queries to the machine. Moreover, the maximum value of ( m ) used in the queries should be as small as possible.

You are provided with a function:

• int Query(int m, std::vector<int> a, std::vector<int> b)

which simulates one query to the machine as described above. Your task is to implement the function

• std::string Solve(int N)

which returns the binary string written on the stone tablet.

Important implementation details:

• Your program must include the header file ancient2.h at the beginning using a preprocessor directive.
• The function Solve is called exactly once per test case and must return a string of length ( N ) consisting only of characters 0 and 1 and exactly equal to the hidden string ( S ).
• If the returned string does not meet these requirements, various Wrong Answer verdicts will be given (e.g. Wrong Answer [1], [2], or [3]).
• You may call the function Query at most 1000 times. Exceeding this limit will result in Wrong Answer [7].

Note: This is an interactive problem. You are not allowed to use standard input/output for communicating with the judge (except for debugging). In the sample grader provided, the file grader.cpp will drive your solution by calling Solve.

In this sample solution we provide a stub that always returns a string of zeros. This solution is correct only if the hidden string ( S ) is actually all zeros. In a full solution you would design a query strategy to determine ( S ) exactly using the allowed queries.

inputFormat

The function Solve receives an integer ( N ), the length of the binary string written on the stone tablet. There is no standard input; instead, the interactive grader calls Solve directly.

outputFormat

The function Solve must return a string of length ( N ) consisting solely of characters 0 and 1 that exactly matches the hidden binary string ( S ) on the stone tablet.

sample

1

0