403851: GYM101341 F Circuits

The world famous scientist Innokentiy created n nuclear circuits. But some of them appeared to be defective, and he forgot which exactly. Luckily, only strictly less than a half of circuits were defective, and now the scientist wants to find out which circuits are operational and which are not.

The scientist can connect two circuits with each other, and each of them will tell whether the other one is operational or not. An operational circuit always gives the right answer, while a defective one can give any answer. Defective circuits can give different answers for the same checks. You should help the scientist to determine which circuits are operational, and do it quickly, because the circuits are, well, nuclear, and if the scientist will not finish in 4n checks, a radiation will cause him irretrievable damage.

This is an interactive problem. Your program should communicate with the jury's program, using standard input and output for that.

At the very beginning, you program gets a single integer n (1 ≤ n ≤ 5000) — the number of circuits.

After that you can make at most 4n checks. To do that, output character «?» and two distinct integers — the numbers of circuits a and b you want to connect and check. Circuits are numbered from one.

As a response you will get two characters, each of which is «+» or «-». The first character is the output of circuit a about condition of circuit b, and the second character is the output of circuit b about condition of circuit a. The character «+» means a circuit is operational, and «-» means it is defective.

As soon as you determine conditions of all circuits, output character «!», then the integer k — the number of operational circuits, and then k distinct integers — their numbers. After that your program must terminate.

5

+ +

- +

+ +

- +

- +

+ +

- +

- -

- +

- -

? 1 2

? 1 3

? 1 4

? 1 5

? 2 3

? 2 4

? 2 5

? 3 4

? 3 5

? 4 5

! 3 1 2 4

Please note that each your message must end with a line break. Also after outputting each message your program must flush the stream buffer, so that the outputted information could reach jury's program: for instance, this can be done by calling «fflush(stdout)» or «cout.flush()» in C++, «System.out.flush()» in Java, «Console.Out.Flush()» in C#, «flush(output)» in Pascal, «sys.stdout.flush()» in Python.