Background

Day 1 Problem C.

The statement is translated from EGOI2021 twincookies.

The official statement does not provide an interaction library. Due to implementation reasons of the interaction library, the testdata may be relatively weak. If you can write an adaptive interaction library, you may contact rui_er.

Problem Description

This is an I/O interactive problem.

Sophie is preparing her sisters' birthday party. They all like cookies. This year, they want to try something new: cookies made by the Unique Cookie Taste Company (UCTC), which produces cookies with different flavors.

Each cookie produced by UCTC has an integer tastiness between $1$ and $10^{16}$. The sisters will be jealous of each other, so the total tastiness of the cookies each sister receives must be the same.

UCTC only accepts orders of exactly $n$ cookies. In each order, the customer specifies the tastiness of each cookie they want.

As the name suggests, the Unique Cookie Taste Company refuses to produce two cookies with the same tastiness for the same customer. Sophie must ensure that she never orders the same tastiness twice, whether within one order or across different orders. Sophie has never ordered from UCTC before, so she can buy each tastiness at most once.

There is one more obstacle for Sophie: it is well known that UCTC's delivery service is extremely bad. When a customer orders $n$ cookies, only one of them will be delivered. The rest are eaten by the delivery staff. The customer cannot decide which cookie will be delivered.

Since the birthday is approaching, Sophie only has time to place at most $101$ orders. Your task is to help her.

More specifically, you need to do the following:

1. First, order cookies. You can place at most $101$ orders, each containing exactly $n$ desired tastiness values. You may place multiple orders. Right after each order is sent, you immediately learn the tastiness of the cookie that gets delivered.

   Remember that you cannot order the same tastiness more than once, even across different orders. (In particular, if you ordered some tastiness values but they were not delivered, you still cannot order the same tastiness again.)

2. Then, share cookies. When you have received enough cookies, you should give the sisters some cookies. Each person should receive at least one cookie, and the total tastiness of the cookies each person receives should be the same. You do not have to distribute all delivered cookies.

Output Format

After each output of your program, you must flush the output stream. This is necessary to ensure the interaction library receives your output immediately.

Some examples:

• In C++, there are several options:
  • fflush(stdout);
  • std::cout << std::flush;
  • std::cout << std::endl; (note that this prints a newline)
  • Reading from std::cin will also flush the output stream.
• In Java, you can use System.out.flush().
• In Python, you can use sys.stdout.flush().

Interaction

Your program should perform the following operations:

1. Read $n$ from standard input.
2. Up to $101$ times:

   1. First, print one line to standard output describing an order of $n$ cookies.

   2. Then, read the tastiness of the delivered cookie.

      It is guaranteed that this number is among the $n$ tastiness values in the current order.

3. Output three lines describing a way to distribute some cookies to the sisters.

The interaction library will write one integer per line.

To order cookies, output one line starting with ? followed by $n$ integers: the tastiness values of the cookies you order. Print a space before each integer.

Remember that you can place at most $101$ orders, and you are not allowed to order the same tastiness value more than once.

When you have received enough cookies, output the final three lines describing the distribution method.

The first line should be ! m k, where $m,k>0$: the numbers of cookies given to the first and second person, respectively.

The second line contains $m$ positive integers separated by spaces: the tastiness values of the cookies received by the first person.

The third line contains $k$ positive integers separated by spaces: the tastiness values of the cookies received by the second person.

Your output must satisfy the following requirements:

1. Each person receives at least one cookie.
2. The total tastiness received by each person is the same.
3. You can only use delivered cookies.
4. Each cookie can be assigned to at most one person.

Any output that satisfies the requirements will be judged AC. In particular, you may output the selected cookies in any order.

After you output the final three lines, flush the output stream one last time and terminate your program normally.

1
13
7
31
12
5
3

? 13
? 7
? 31
? 12
? 5
? 3
! 2 3
7 13
12 5 3

2
7
2
5

? 3 7
? 2 8
? 1 5
! 2 1
2 5
7

Hint

Hint

The sample input and output should be read line by line. Your program alternates between reading one integer from standard input and printing one line to standard output (or the final three lines).

The interaction library chooses the delivered cookie arbitrarily. This means that in some test points, the interaction library may be adaptive; but in other test points, it may choose randomly. In particular, for $n=2$, if you output the same orders as in sample $2$, you may get different results.

Constraints

For all data, $1\le n\le 5\times 10^3$.

• Subtask 1 ($8$ points): $n=1$.
• Subtask 2 ($9$ points): $n\le 2$.
• Subtask 3 ($18$ points): $n\le 25$.
• Subtask 4 ($16$ points): $n\le 200$.
• Subtask 5 ($13$ points): $n\le 10^3$.
• Subtask 6 ($36$ points): no special restrictions.

Translated by ChatGPT 5