#P1365G. Secure Password

    ID: 1470 Type: RemoteJudge 2000ms 256MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>bitmaskscombinatoricsconstructive algorithmsinteractivemath*2800

Secure Password

No submission language available for this problem.

Description

This is an interactive problem.

Ayush devised yet another scheme to set the password of his lock. The lock has nn slots where each slot can hold any non-negative integer. The password PP is a sequence of nn integers, ii-th element of which goes into the ii-th slot of the lock.

To set the password, Ayush comes up with an array AA of nn integers each in the range [0,2631][0, 2^{63}-1]. He then sets the ii-th element of PP as the bitwise OR of all integers in the array except AiA_i.

You need to guess the password. To make a query, you can choose a non-empty subset of indices of the array and ask the bitwise OR all elements of the array with index in this subset. You can ask no more than 13 queries.

The first line of input contains one integer nn (2n1000)(2 \le n \le 1000) — the number of slots in the lock.

Interaction

To ask a query print a single line:

  • In the beginning print "? c " (without quotes) where cc (1cn)(1 \leq c \leq n) denotes the size of the subset of indices being queried, followed by cc distinct space-separated integers in the range [1,n][1, n].

For each query, you will receive an integer xx — the bitwise OR of values in the array among all the indices queried. If the subset of indices queried is invalid or you exceeded the number of queries then you will get x=1x = -1. In this case, you should terminate the program immediately.

When you have guessed the password, print a single line "! " (without quotes), followed by nn space-separated integers  — the password sequence.

Guessing the password does not count towards the number of queries asked.

The interactor is not adaptive. The array AA does not change with queries.

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. To do this, use:

  • fflush(stdout) or cout.flush() in C++;
  • System.out.flush() in Java;
  • flush(output) in Pascal;
  • stdout.flush() in Python;
  • see the documentation for other languages.

Hacks

To hack the solution, use the following test format:

On the first line print a single integer nn (2n1000)(2 \le n \le 1000) — the number of slots in the lock. The next line should contain nn space-separated integers in the range [0,2631][0, 2^{63} - 1] — the array AA.

Input

The first line of input contains one integer nn (2n1000)(2 \le n \le 1000) — the number of slots in the lock.

Samples

Sample Input 1

3

1

2

4

Sample Output 1

? 1 1

? 1 2

? 1 3

! 6 5 3

Note

The array AA in the example is {1,2,4}\{{1, 2, 4\}}. The first element of the password is bitwise OR of A2A_2 and A3A_3, the second element is bitwise OR of A1A_1 and A3A_3 and the third element is bitwise OR of A1A_1 and A2A_2. Hence the password sequence is {6,5,3}\{{6, 5, 3\}}.