It is well known that the Central Intelligence Agency is tasked with gathering, processing and analyzing national security information. It is also suspected that they own quite large collections of commonly-used computer passwords and are developing some quite sophisticated tools that are capable of compromising password-protected computer systems.
The tables have turned, your task is to compromise the security of a CIA server. Good luck!
Naturally, they are well aware of typical patterns that humans produce while coming up with their
passwords, so attempts such as 123456
, password
, 1q2w3e4r
or welcome
are futile. Luckily, we have
uncovered certain pieces of information that might be of use to you.
Namely, their master password consists of exactly characters, where is an even number. Exactly
half of those characters is equal to the open parenthesis ((
), while the other half is equal to the closing
parenthesis ()
). Additionally, instead of the usual "forgot your password?" functionality, their engineers
have decided to expose an API to the forgetful administrator. Using the API, an administrator can
execute at most queries asking "whether the interval of the password from -th to the -th character is
mathematically valid".
The mathematical validity of a sequence of parentheses is defined inductively as:
- is a mathematically valid sequence.
- If is a mathematically valid sequence, then is a mathematically valid sequence as well.
- If both and are mathematically valid sequences, then is also mathematically valid.
Interaction
This is an interactive task. Your program must communicate with a program made by the organizers which simulates the functionality of a fictitious insecure CIA server from the task description.
Before interaction, your program should read an even integer and an integer from the standard input. The meaning of both numbers is described in the task statement.
After that, your program can send query requests by writing to the standard output. Each query must be
printed in a separate line and have the form ? a b
, where holds. After each query has
been written, your program should flush the output and read the answer from the standard input. The
answer is a if the interval of the password starting from -th and ending at the -th character forms a
mathematically valid sequence of parentheses. Otherwise, the answer is . Your program can make at
most such queries.
After your program has deduced the secret password, it should write a line to the standard output in the
form ! x1 x2 ... xN
, where characters represent the characters of the secret password.
After that, your program should flush the output once more and gracefully terminate its execution.
Note: You can download the sample source code from the judging system that correctly interacts with the CIA server, including the output flush.
Constraints
Subtask | Points | Constraints |
---|---|---|
1 | 14 | , the whole password is a mathematically valid sequence. |
2 | 7 | |
3 | 57 | , the whole password is a mathematically valid sequence. |
4 | 22 |
Sample Interaction
>>>
denotes your output. Do not print this out.
The sequence is ((()))
.
6 9
>>> ? 1 6
1
>>> ? 1 2
0
>>> ? 2 4
0
>>> ? 2 5
1
>>> ? 3 4
1
>>> ! ((()))
Explanation for Sample Interaction
The secret password is ((()))
of length , and a program may ask at most queries.
For the first query, the whole password is mathematically valid.
For the second query, ((
isn't mathematically valid.
For the third query, (()
isn't mathematically valid.
For the fourth query, (())
is mathematically valid.
For the fifth query, ()
is mathematically valid.
The answer matches the password, and the CIA is compromised.
Comments