Politicians and Competitive Programmers

This is an interactive problem

There are $n$ citizens in SmartLand, numbered from $0$ to $n-1$. Surprisingly, each of them is either politician or a competitive programmer (but not both), and everyone in the SmartLand knows who the others are. Of course, competitive programmers always tell truth and politicians always lie.

You want to determine, for each citizen of SmartLand, whether he is a politician or a competitive programmer. To do this, you can do the following:

• Choose three distinct citizens $X$, $Y$, $Z$, and ask $X$ the following question: "Is it true that $Y$ would answer "Yes" to the question "Is $Z$ competitive programmer?""

However, there is an important constraint: You can't ask the same citizen twice. That is, each citizen can be chosen as $X$ at most once.

Determine for each citizen, whether they are competitive programmers or politicians.

Qarşılıqlı təsir

Start by reading an integer $n$ ($5\le n\le 1000$) — the number of citizens of SmartLand.

To ask the question, output:

? $X$ $Y$ $Z$

Here $X$, $Y$, $Z$ must be distinct integers with $0\le X,Y,Z\le n-1$, and $X$ couldn't have been asked questions before.

In response, the interactor will output $1$, if $X$ answers "Yes", and $0$ otherwise.

When you want to output answer, output:

! $s$

Here $s$ is a binary string of length $n$, and $s_i$ should be $1$, if citizen $i$ is competitive programmer, and $0$ if he is politician.

Make sure to exit immediately to avoid getting other verdicts.

If you ask the invalid query, you will receive a verdict Wrong Answer.

After printing a query do not forget to output the end of the line and flush the output. Otherwise, you will get Idleness limit exceeded verdict.

To do this, use:

• fflush(stdout) or cout.flush() in C++;

• System.out.flush() in Java;

• stdout.flush() in Python;

It is guaranteed that the roles of all citizens are fixed before the start of the interaction. In other words, the interactor is not adaptive.

Nümunələr

Qeyd

In the sample, citizens $0$, $1$, $2$, $3$ are competitive programmers, and citizen $4$ is politician.

Note that the queries in the sample are not sufficient to determine who each citizen is, but nobody forbids you to answer anyways...