This is an interactive problem.
There is a hidden sequence of length . Every element is , , or , and each of the three values occurs at least once.
The attacker may make at most comparisons. In a comparison, the attacker selects distinct positions and asks for the order relation between and . The defender replies less than, equal to, or greater than. The defender need not choose a sequence in advance and may adapt its replies to previous queries. However, at least one valid sequence consistent with every reply so far must always exist.
The attacker wins by uniquely determining the sequence from the comparison results. The defender wins if at least two sequences remain possible after at most comparisons. Merely guessing a sequence does not count as an attacker victory.
Given , choose a role that has a guaranteed winning strategy and execute that strategy. The judge plays the opponent. Your strategy must guarantee victory against every valid behavior of the opponent.
When playing the defender, submit two distinct valid sequences consistent with all your replies at the end.
Initially, you receive in the following format:
One execution contains one game. Subsequent input depends on the selected role and follows the protocol below.
Role selection
On the first line, print A for attacker or D for defender. Selecting a role without a guaranteed winning strategy against every valid behavior of the opponent is Wrong Answer.
Attacker To compare two positions, print:
?
Require and . The judge returns if , if they are equal, and if . Repeated pairs are allowed, but every query counts. You may make at most queries.
This example selects the attacker. The replies uniquely determine . Sample input lists the judge messages, while sample output lists the contestant messages in order; during execution they are exchanged interactively.
This example selects the defender. Both witnesses and satisfy that the first element is less than the second and the second is greater than the third. Actual queries may differ from this example.
-101Once the sequence is uniquely determined, print the following and terminate immediately:
!
Your sequence must be the unique valid sequence consistent with all replies so far. If another sequence is possible, the answer is rejected.
Defender The judge sends at most queries of the form:
?
Reply with -1, 0, or 1, meaning , , or , respectively. At least one valid sequence must remain consistent with all replies.
When the judge sends the single token !, querying has ended. The judge may stop before making queries. Print two distinct sequences in the following format and terminate immediately:
!
Each sequence must have length , use only , , and , and contain each value at least once. They must differ at some position, and both must agree with every previous reply.
Flush the output buffer after every output. Exceeding the query limit, invalid indices or tokens, inconsistent replies, or an invalid final answer may result in Wrong Answer. Failure to flush or waiting when no input will arrive may result in Time Limit Exceeded. Terminate immediately on end of input. Do not wait for more input after the final output. Repeated whitespace between tokens and an optional final newline do not affect judging.