This is an interactive problem!
In the new game "Onu" invented by Gulnoza, there are \(N\) types of cards, with numbers from \(1\) to \(N\) written on them. There are \(2N\) cards in total in the game, with exactly \(2\) copies of each type. Cards with the same number written on them are called pairs.
Yahyo laid all the cards face down in a row. Yahyo can see what number is written on the cards, but Gulnoza cannot. Gulnoza's task is to find all the pairs by asking Yahyo queries. For this, in one query Gulnoza selects a set of cards, and Yahyo tells her how many distinct types of cards are in that set.
Help Gulnoza!
At the start of the program you are given the number \(N\), i.e. the number of distinct card types. To make a query, print to the screen in the format:
? k a[1] a[2] ... a[k]
Here \(k\) is the number of elements in the chosen set of cards, and \(a[i]\) are the card indices. The indices must be printed in increasing order, i.e. \(1 \le a[1] < a[2] < \ldots < a[k] \le 2N\).
Then read the number \(d\) from the input – the number of distinct cards in the set.
Once you have found the answer, print it in the format:
! x[1] y[1] x[2] y[2] ... x[N] y[N]
where cards \(x[i]\) and \(y[i]\) must be of the same type.
For example, let \(N = 4\) and suppose Yahyo arranged the cards as \([2, 3, 2, 1, 4, 4, 3, 1]\). That is, the pairs of cards with the same numbers are \((4, 8)\), \((1, 3)\), \((2, 7)\) and \((5, 6)\).
In the first query, Gulnoza asks about the cards at indices \([1, 2, 3]\). These cards have the numbers \([2, 3, 2]\) written on them. Since there are \(2\) distinct types in total, Yahyo answers \(2\).
If Gulnoza queries \([2, 4, 6, 7]\), Yahyo answers \(3\), because among the numbers \([3, 1, 4, 3]\) there are \(3\) distinct values.
After that, Gulnoza answers \([2, 7, 5, 6, 1, 3, 8, 4]\). That is, cards \(2\) and \(7\) have the same number, cards \(5\) and \(6\) have the same number, and so on.
Note that if Gulnoza answered \([7, 2, 5, 6, 1, 3, 8, 4]\) or \([8, 4, 3, 1, 2, 7, 6, 5]\), her answer would also be considered correct.
| INPUT | OUTPUT |
|---|---|
? 3 1 2 3 | |
2 | |
? 4 2 4 6 7 | |
3 | |
! 2 7 5 6 1 3 8 4 |
Additionally, partial score is available in subtask 4. Let \(q\) be the maximum number of queries you used across the tests of subtask 4. Then you score:
| Condition | Points |
|---|---|
| \(20\,000 < q\) | \(0\) |
| \(10\,000 < q \le 20\,000\) | \(15\) |
| \(2300 < q \le 10\,000\) | \(15 + 50 \cdot \frac{2300}{q}\) |
| \(q \le 2300\) | \(65\) |