During the pandemic of $$$2020$$$, the Brazilian Final of the Programming Marathon had to be held online. Before the competition started, participants could access the website, but the password would only be released when the competition began. Curious about security and programming, you decide to test a classic timing attack known as a timing attack.

The idea behind this type of attack is that, often, when comparing two strings, the verification function returns false as soon as it finds an incorrect character in the prefix. This means that the more correct characters you provide at the beginning of the string, the longer the response time tends to be. This problem is inspired by this principle.

// Function that compares if two strings are equal,
// stopping when any value in the prefix is different.
int isEqual(const std::string& a, const std::string& b) {
    if(a.size() != b.size()) return 0;
    for (int i = 0; i < a.size(); ++i) {
        if (a[i] != b[i]) {
            return 0;
        }
    }
    return 1;
}

You need to discover a hidden binary password, represented by a string $$$S$$$ of size $$$1 \leq N \leq 1000$$$, using only interactive queries.

• For each query, you send a binary string of size $$$N$$$.
• The judge will compare your string with the password $$$S$$$ and return an integer $$$T'$$$ based on the actual number of correct characters $$$T$$$ of the largest common prefix.
• The returned value $$$T'$$$ will be:
  • $$$T - 1$$$, $$$T$$$, or $$$T + 1$$$ with some fixed probability (not necessarily uniform).
  • If $$$T = 0$$$, the return will always be $$$1$$$ (never $$$0$$$ or negative).
  • If $$$T = 1$$$, the return will always be $$$1$$$ or $$$2$$$ (never $$$0$$$).
  • If the password is correct, the judge will return $$$1000000$$$ and you can terminate your program.
  • If you exceed the allowed number of queries or make an incorrect query, the judge will return $$$-1$$$.

You can use at most $$$3500$$$ queries.

The algorithm to obtain the largest common prefix is given below:

// a.size() == N and b.size() == N
int commonPrefix(const std::string& a, const std::string& b){
    int correct = 0;
    while(correct < N && a[correct] == b[correct])
        correct++;
    return correct;
}