310578: CF1854D. Michael and Hotel

D. Michael and Hoteltime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Michael and Brian are stuck in a hotel with $n$ rooms, numbered from $1$ to $n$, and need to find each other. But this hotel's doors are all locked and the only way of getting around is by using the teleporters in each room. Room $i$ has a teleporter that will take you to room $a_i$ (it might be that $a_i = i$). But they don't know the values of $a_1,a_2, \dots, a_n$.

Instead, they can call up the front desk to ask queries. In one query, they give a room $u$, a positive integer $k$, and a set of rooms $S$. The hotel concierge answers whether a person starting in room $u$, and using the teleporters $k$ times, ends up in a room in $S$.

Brian is in room $1$. Michael wants to know the set $A$ of rooms so that if he starts in one of those rooms they can use the teleporters to meet up. He can ask at most $2000$ queries.

The values $a_1, a_2, \dots, a_n$ are fixed before the start of the interaction and do not depend on your queries. In other words, the interactor is not adaptive.

Input

The input contains a single integer $n$ ($2 \leq n \leq 500$).

Interaction

To ask a query, print a line in the format "? u k |S| S_1 S_2 ... S_|S|" with $1 \leq u, S_1, \ldots, S_{|S|} \leq n$, all the $S_i$ distinct, and $1 \leq k \leq 10^9$.

As a response to the query you will get "1" if the answer is yes, and "0" if the answer is no.

To output an answer, you should print "! |A| A_1 A_2 ... A_|A|" with $1 \leq A_1, \ldots, A_{|A|} \leq n$ all distinct. Printing the answer doesn't count as a query.

See the interaction example for more clarity.

If you ask too many queries or you ask a malformed query, you will get Wrong answer.

After printing a query do not forget to output the end of 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.

Hack format

For the hacks use the following format.

The first line should contain $n$ — the number of rooms.

The second line should contains $n$ integers $a_1, a_2, \dots, a_n$ — the teleporter in room $i$ leads to room $a_i$.

ExampleInput

5

0

1

Output

? 3 5 2 2 3

? 2 5 2 2 3

! 3 1 3 4

Note

In the sample test, there are $n=5$ rooms and the (hidden) array describing the behavior of the teleporters is $[1, 2, 1, 3, 2]$.

• The first query asks whether starting from room number $a=3$, and using the teleporters $5$ times, one ends up in one of the two rooms $S=\{2, 3\}$. This action results in ending up in the room $1$, so the answer is $0$.
• The second query asks whether starting from room number $a=2$, and using the teleporters $5$ times, one ends up in one of the two rooms $S=\{2, 3\}$. This action results in ending up in the room $2$, so the answer is $1$.

题目大意：
题目描述了迈克和布莱恩在一个有n个房间的酒店中，每个房间都有一个传送器，可以将人传送到房间a_i（可能a_i=i）。他们不知道a_1,a_2,...,a_n的值。他们可以通过向前台查询来寻找对方。在每次查询中，他们可以给出一个房间u，一个正整数k，以及一个房间集合S。酒店接待员会回答从房间u开始，使用传送器k次后，是否会到达集合S中的某个房间。布莱恩在房间1，迈克想要知道如果他从集合A中的某个房间开始，他们是否可以通过传送器相遇。他最多可以询问2000次。a_1,a_2,...,a_n的值在交互开始前就已经确定，与查询无关。

输入输出数据格式：
输入：一个整数n（2≤n≤500）。
查询：以格式"? u k |S| S_1 S_2 ... S_|S|"打印一行，其中1≤u, S_1, ..., S_|S|≤n，所有S_i都互不相同，1≤k≤10^9。
响应：如果答案为是，则输出"1"，否则输出"0"。
输出：以格式"! |A| A_1 A_2 ... A_|A|"打印一行，其中1≤A_1, ..., A_|A|≤n，所有A_i都互不相同。打印答案不计入查询次数。题目大意： 题目描述了迈克和布莱恩在一个有n个房间的酒店中，每个房间都有一个传送器，可以将人传送到房间a_i（可能a_i=i）。他们不知道a_1,a_2,...,a_n的值。他们可以通过向前台查询来寻找对方。在每次查询中，他们可以给出一个房间u，一个正整数k，以及一个房间集合S。酒店接待员会回答从房间u开始，使用传送器k次后，是否会到达集合S中的某个房间。布莱恩在房间1，迈克想要知道如果他从集合A中的某个房间开始，他们是否可以通过传送器相遇。他最多可以询问2000次。a_1,a_2,...,a_n的值在交互开始前就已经确定，与查询无关。 输入输出数据格式： 输入：一个整数n（2≤n≤500）。 查询：以格式"? u k |S| S_1 S_2 ... S_|S|"打印一行，其中1≤u, S_1, ..., S_|S|≤n，所有S_i都互不相同，1≤k≤10^9。 响应：如果答案为是，则输出"1"，否则输出"0"。 输出：以格式"! |A| A_1 A_2 ... A_|A|"打印一行，其中1≤A_1, ..., A_|A|≤n，所有A_i都互不相同。打印答案不计入查询次数。