CF1491F Magnets

This is an interactive problem. Kochiya Sanae is playing with magnets. Realizing that some of those magnets are demagnetized, she is curious to find them out. There are $ n $ magnets, which can be of the following $ 3 $ types: - N - S - - — these magnets are demagnetized. Note that you don't know the types of these magnets beforehand. You have a machine which can measure the force between the magnets, and you can use it at most $ n+\lfloor \log_2n\rfloor $ times. You can put some magnets to the left part of the machine and some to the right part of the machine, and launch the machine. Obviously, you can put one magnet to at most one side (you don't have to put all magnets). You can put the same magnet in different queries. Then the machine will tell the force these magnets produce. Formally, let $ n_1,s_1 $ be the number of N and S magnets correspondently on the left and $ n_2,s_2 $ — on the right. Then the force between them would be $ n_1n_2+s_1s_2-n_1s_2-n_2s_1 $ . Please note that the force is a signed value. However, when the absolute value of the force is strictly larger than $ n $ , the machine will crash into pieces. You need to find all magnets of type - (all demagnetized ones), without breaking the machine. Note that the interactor is not adaptive. The types of the magnets are fixed before the start of the interaction and do not change with queries. It is guaranteed that there are at least $ 2 $ magnets whose type is not -, and at least $ 1 $ magnet of type -.

N/A

N/A

The empty lines in the sample are just for you to better understand the interaction process. You're not required to print them. In the sample, the types of the magnets are NN--. At first, you put the third magnet on the left and the fourth one on the right. Both of them have type -, thus no force is produced. Then you put the first magnet on the left and the second and third one on the right. The third magnet has type -, while the other two magnets are of type N, so the force produced is $ 1 $ . In the following two queries, the force is $ 0 $ since there is only a magnet with property - on the right. Then we can determine that the magnets of type - are the third and the fourth one, so we should print ! 2 3 4 and exit.