Two cookies

This is an interactive problem. Your program will communicate with our grader by writing to the standard output and reading from the standard input.

Sophie is planning a birthday celebration for her twins, who adore cookies. For their special day, they want to try something new: cookies from the Unique Cookie Tastiness Company (UCTC).

Each cookie from UCTC has an integer sweetness value ranging from $1$ to $10^{16}$ inclusive. Since Sophie's twins are competitive, each must receive cookies with the same total sweetness.

UCTC only accepts orders of exactly $n$ cookies. For each order, the client specifies the sweetness of each of the $n$ cookies they desire.

True to its name, the Unique Cookie Tastiness Company will not produce two cookies with the same sweetness for a single client. Sophie must ensure she never orders the same sweetness twice—neither within a single order nor across different orders. As Sophie has never purchased cookies from UCTC before, she can order cookies of each sweetness at most once.

There's another challenge: UCTC's delivery service is notoriously unreliable. Whenever a client orders $n$ cookies, only one of these $n$ cookies actually reaches the client. The rest are consumed by the delivery staff. Sophie cannot control which of the ordered $n$ cookies will be delivered.

With the birthday approaching, Sophie can make at most 101 orders. Your task is to assist her.

Here's what you need to do:

1. First, order cookies. You can make up to 101 orders, each consisting of exactly $n$ desired sweetness values. You make one order at a time. Immediately after each order, you will receive the sweetness of one cookie that was actually delivered.

   Remember, you cannot use the same sweetness value more than once, even across different orders. (Specifically, if you order a cookie with some sweetness $t$, but it does not arrive, you can order a cookie with the same sweetness again.)

2. Then, divide the cookies. Once you have received enough cookies, you must divide some cookies between the twins. Both twins must receive at least one cookie, and each twin must receive cookies with the same total sweetness. You do not have to use all the cookies you received.

Interaction

Your program should perform the following sequence of actions:

1. Read the number $n$ from the standard input.

2. Up to 101 times:

   • First, output one line describing $n$ cookies to the standard output.

   • Then read the sweetness of the cookie you received from the standard input. It is guaranteed that this value is among the $n$ values that were just output by the participant.

3. Output three lines describing one valid way to give some of the received cookies to the twins.

The grader will output each integer on a separate line.

To order cookies, output one line with the character ?, followed by $n$ integers: the sweetness values of the cookies you want to order. Output one space before each of the $n$ integers.

Remember that you can make at most 101 orders and that you are not allowed to use the same sweetness value twice.

After you have ordered enough cookies, output the last three lines describing which cookies Sophie should give to the twins.

The first of these lines should be of the form «! $m$ $k$» where $m,k>0$: the number of cookies that the first and second twin should receive, respectively.

The second of these lines should contain $m$ integers, separated by single spaces: the sweetness values of the cookies the first twin should receive.

The third of these lines should contain $k$ integers, separated by single spaces: the sweetness values of the cookies the second twin should receive.

The output must meet the following conditions:

• Each twin must receive at least one cookie.

• Each twin must receive cookies with the same total sweetness.

• Only cookies that you actually received after orders can be used.

• Each of these cookies can be given to only one of the twins.

Any output that meets these conditions will be accepted. In particular, you can output the selected cookies in any order.

After you output the last three lines, perform the 'flush' operation one last time, and then terminate the program normally.

Output

Every time your program outputs one or more lines to the standard output, you must perform the 'flush' operation. This is necessary so that the data you output is immediately sent to the grader.

Examples of how to do this:

• In C++, there are several ways to do this.

  • fflush(stdout);

  • std::cout << std::flush;

  • std::cout << std::endl; (note that this operation also outputs an extra line)

• In Java, you can use System.out.flush()

• In Python, you can use sys.stdout.flush()

Examples

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

Note

Examples of input and output should be read line by line. Your program alternately reads one value from the standard input and outputs one line (or three lines at the end) to the standard output.

The grader chooses which cookie to return arbitrarily. This means that the grader can be adaptive to your requests in some tests, but it can also choose random cookies in other tests. In particular, for $n=2$, if you make the same sequence of orders as in the second example, you may receive a different set of cookies.

Scoring

Block 1 (8 points): $n=1$

Block 2 (9 points): $1\le n\le 2$

Block 3 (18 points): $1\le n\le 25$

Block 4 (16 points): $1\le n\le 200$

Block 5 (13 points): $1\le n\le 1000$

Block 6 (36 points): $1\le n\le 5000$