Два печенья

Это интерактивная задача. Ваша программа будет взаимодействовать с нашим грейдером, выводя данные в стандартный вывод и считывая данные из стандартного ввода.

Софи готовит день рождения для своих близнецов, которые обожают печенье. На этот раз они хотят попробовать что-то новое: печенье от компании Unique Cookie Tastiness Company (UCTC).

Каждое печенье от UCTC имеет целочисленное значение сладости от $1$ до $10^{16}$ включительно. Поскольку близнецы Софи завидуют друг другу, каждому из них нужно получить печенье с одинаковой суммарной сладостью.

UCTC принимает заказы только на ровно $n$ печений. В каждом заказе клиент указывает сладость каждого из $n$ печений, которые он хочет.

Компания UCTC, верная своему названию, не производит два печенья с одинаковой сладостью для одного клиента. Софи должна убедиться, что она никогда не заказывает одно и то же значение сладости дважды — ни в одном заказе, ни в разных заказах. Поскольку Софи никогда ранее не покупала печенье в UCTC, она может заказать печенье каждой сладости не более одного раза.

Есть еще одна проблема: служба доставки UCTC известна своей ненадежностью. Каждый раз, когда клиент заказывает $n$ печений, только одно из них действительно доходит до клиента, остальные съедаются сотрудниками службы доставки. Софи не может контролировать, какое из заказанных $n$ печений будет доставлено.

Поскольку день рождения уже скоро, у Софи есть время сделать не более 101 заказа. Ваша задача — помочь ей.

Конкретно, вам нужно сделать следующее:

1. Сначала закажите печенье. Вы можете сделать не более 101 заказа, каждый из которых состоит ровно из $n$ желаемых значений сладости. Вы делаете один заказ за раз. Сразу после каждого заказа вы получаете сладость одного печенья, которое вам фактически доставили.

   Помните, что вам не разрешается использовать одно и то же значение сладости несколько раз, даже для разных заказов. (В частности, если вы заказываете печенье с некоторой сладостью $t$, но оно не пришло, вы сможете заказать печенье с такой же сладостью снова.)

2. Затем разделите печенье. Получив достаточное количество печений, вы должны разделить некоторые из них между близнецами. Оба близнеца должны получить по крайней мере одно печенье, а каждый близнец должен получить печенье с одинаковой суммарной сладостью. Вам не обязательно использовать все полученные печенья.

Протокол взаимодействия

Ваша программа должна выполнять следующую последовательность действий:

1. Считать число $n$ из стандартного ввода.

2. Не более 101 раза:

   • Сначала выведите одну строку, описывающую $n$ печений, в стандартный вывод.

   • Затем считайте сладость печенья, которое вы получили из стандартного ввода. Гарантируется, что это значение находится среди $n$ значений, которые были только что выведены участником.

3. Выведите три строки, которые описывают один валидный способ подарить некоторые из полученных печений близнецам.

Грейдер выведет каждое целое число в отдельной строке.

Чтобы заказать печенье, выведите одну строку с символом ?, а затем $n$ целых чисел: значения сладости печений, которые вы хотите заказать. Выведите по одному пробелу перед каждым из $n$ целых чисел.

Помните, что вы можете сделать не более 101 заказа и что вам не разрешается использовать одно и то же значение сладости дважды.

После того, как вы заказали достаточное количество печений, выведите последние три строки, которые описывают, какие печенья Софи должна дать близнецам.

Первая из этих строк должна иметь вид «! $m$ $k$», где $m,k>0$: количество печений, которые должны получить, соответственно, первый и второй близнецы.

Вторая из этих строк должна содержать $m$ целых чисел, разделенных одиночными пробелами: значения сладости печений, которые должен получить первый близнец.

Третья из этих строк должна содержать $k$ целых чисел, разделенных одиночными пробелами: значения сладости печений, которые должен получить второй близнец.

Вывод должен соответствовать следующим условиям:

• Каждый близнец должен получить по крайней мере одно печенье.

• Каждый близнец должен получить печенье с одинаковой суммарной сладостью.

• Использовать можно только печенья, которые вы фактически получили после заказов.

• Каждое из этих печений может быть предоставлено только одному из близнецов.

Будет принят любой вывод, который соответствует этим условиям. В частности, вы можете выводить выбранные печенья в любом порядке.

После того, как вы выведете последние три строки, последний раз выполните операцию 'flush', а затем нормально завершите программу.

Выходные данные

Каждый раз, когда ваша программа выводит одну или несколько строк в стандартный вывод, вы должны выполнять операцию 'flush'. Это необходимо для того, чтобы данные, которые вы вывели, сразу поступали к грейдеру.

Примеры того, как это можно сделать:

• В C++, есть несколько вариантов как это сделать.

  • fflush(stdout);

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

  • std::cout << std::endl; (обратите внимание, что эта операция также выводит лишнюю строку)

• В Java, вы можете использовать System.out.flush()

• В Python, вы можете использовать sys.stdout.flush()

Примеры

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

Примечание

Примеры ввода и вывода следует читать строка за строкой. Ваша программа поочередно считывает одно значение из стандартного ввода и выводит одну строку (или три строки в конце) в стандартный вывод.

Грейдер выбирает, какое печенье возвращать произвольно. Это означает, что грейдер может быть адаптивным к вашим запросам в некоторых тестах, но он также может выбрать случайные печенья в других тестах. В частности, для $n=2$, если вы сделаете ту же последовательность заказов, что и во втором примере, вы можете получить другой набор печений.

Оценивание

Блок 1 (8 баллов): $n=1$

Блок 2 (9 баллов): $1\le n\le 2$

Блок 3 (18 баллов): $1\le n\le 25$

Блок 4 (16 баллов): $1\le n\le 200$

Блок 5 (13 баллов): $1\le n\le 1000$

Блок 6 (36 баллов): $1\le n\le 5000$