C. 28 ударов ножом
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это интерактивная задача

Представьте, что вы оказались в одной небезызвестной игре следователем. Вам предстоит разоблачить $$$n$$$ девиантов, которые совершили вопиющие преступления. У каждого андроида $$$i$$$ есть мера наказания $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$, $$$a_i$$$ — целое) и параметр стресса $$$c_i$$$, изначально равный нулю. Так как времени у нас мало, вам предстоит провести параллельный допрос. Одним вопросом вы можете выкрикнуть во всеуслышанье (все не сознавшиеся девианты услышат ваше заявление) «$$$X$$$ ударов ножом! Ты действовал наверняка!». Каждый девиант воспринимает это высказывание на свой счет и начинает думать:

  • Если $$$X \gt a_i$$$, девиант будет уверен, что вы не знаете, что он совершил преступление, а просто гадаете, поэтому после этого он перестанет реагировать на любые вопросы.
  • Если $$$X \le a_i$$$, девиант получает $$$X$$$ единиц стресса, потому что уверен, что вы вот вот раскроете его грехи. То есть $$$c_i := c_i + X$$$ (значение $$$c_i$$$ увеличивается на $$$X$$$).
После любого вопроса если уровень стресса $$$c_i$$$ будет не меньше меры наказания, то он сознается и начнёт всех сдавать, но сделает это по-хитрому: назовёт сумму наказаний себя и другого девианта. Более формально, когда будет верно $$$c_i \ge a_i$$$, андроид $$$i$$$ скажет про каждого подельника $$$j$$$ число $$$a_i + a_j$$$, $$$i \neq j$$$.

Когда девиант сознался, он выходит из комнаты допроса и не слышит никакие дальнейшие вопросы.

Ваша задача заключается в том, чтобы все девианты сознались, а также узнать их меры наказания. Если хотя бы один девиант не сознался, вы получите вердикт Wrong Answer даже если выведите правильные меры наказания. Также в некоторых подгруппах от вас не будет требоваться узнать меры наказаний, достаточно лишь добиться того, что все сознались.

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

В единственной строке вводится три целых числа $$$n$$$, $$$k$$$, $$$t$$$ ($$$3 \le n \le 100$$$, $$$30 \le k \le 1000$$$, $$$0 \le t \le 1$$$) — количество девиантов в участке, максимальное количество вопросов, которое можно задать, и параметр, отвечающий за то, нужно ли выводить все меры наказаний или достаточно лишь, чтобы все сознались.

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

В этой задаче вы можете делать вопросы двух типов:

  • «$$$?$$$ $$$X$$$» ($$$1 \le X \le 10^9$$$). Вы совершаете обвинение с $$$X$$$ ударами.

    После очередного запроса интерактор возвращает следующие данные:

    В первой строке вводится число $$$m$$$ ($$$0 \le m \le n$$$), количество девиантов, которые хотят признаться.

    В следующих $$$m$$$ строках вводится по $$$n + 1$$$ числу: $$$j$$$ и $$$n$$$ чисел $$$b_i$$$, где $$$b_i = a_j + a_i$$$ для всех $$$j \neq i$$$. Для $$$i = j$$$, $$$b_i = 0$$$. Номер признающегося девианта и информация про подельников соответственно.

    Гарантируется, что каждый девиант, если признается, будет признаваться только один раз.

  • «$$$!$$$ $$$a_1\ a_2\ \dots\ a_n$$$». Этот вопрос означает, что вы готовы сказать все меры наказаний и допрос на этом заканчивается и ваша программа должна немедленно завершиться. Если не все девианты сознались, вы получите вердикт Wrong answer. Все выведенные вами числа $$$a_i$$$ должны быть целыми, а также должно быть верно $$$0 \le a_i \le 10^9$$$ ($$$0$$$ обозначает, что вы не знаете меру наказания). Если хотя бы одно число нецелое или вне этого диапазона — вы получите вердикт Wrong answer. Также, если $$$t = 1$$$ и вы вывели хотя бы одну неверную меру наказания, вы получите вердикт Wrong answer.

    После совершения данного запроса, ваша программа должна завершиться.

Вы можете сделать не более $$$k$$$ запросов первого типа и только один запрос второго типа. Даже если вы заставили всех андроидов признаться, но не можете определить их меры наказания, программа должна завершаться запросом второго типа.

Интерактор в данной задаче является неадаптивным

После вывода каждого запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для этого используйте:

  • fflush(stdout) или cout.flush() в C++;
  • sys.stdout.flush() в Python;
  • смотрите документацию для других языков.
Система оценки
№Доп. ограниченияБаллыНеобх. группыКомментарий
$$$k$$$$$$a_i$$$$$$t$$$
$$$0$$$—————Тесты из условия
$$$1$$$$$$k = \max(n, 30)$$$—$$$t=0$$$$$$6$$$—$$$a_1 = 1$$$
$$$2$$$$$$t=1$$$$$$7$$$$$$1$$$
$$$3$$$$$$k = 1000$$$$$$a_i \le 1000$$$$$$ t=0$$$$$$9$$$——
$$$4$$$$$$t=1$$$$$$10$$$$$$3$$$
$$$5$$$$$$a_i \le 5 \cdot 10^5$$$$$$t = 0$$$$$$10$$$$$$3$$$—
$$$6$$$$$$t=1$$$$$$11$$$$$$3-5$$$
$$$7$$$$$$k = 30$$$—$$$t=0$$$$$$8$$$—$$$a_i$$$ — степень двойки
$$$8$$$$$$t=1$$$$$$8$$$$$$7$$$
$$$9$$$$$$t=0$$$$$$15$$$$$$1,3,5,7$$$—
$$$10$$$$$$t=1$$$$$$16$$$$$$0-9$$$
Примеры
Входные данные
4 30 0

1
1 0 8 7 9

3
2 8 0 9 11
3 7 9 0 10
4 9 11 10 0
Выходные данные

? 3


? 3




! 0 0 0 0
Входные данные
4 30 1

1
1 0 8 7 9

3
2 8 0 9 11
3 7 9 0 10
4 9 11 10 0
Выходные данные

? 3


? 3




! 3 5 4 6
Примечание

Разберем, что происходит в примере:

Сначала прозвучало "3 удара ножом". Первый девиант сознался поскольку его стресс достиг его меры наказания ($$$0 + 3 \ge 3$$$). Стресс всех андроидов: $$$3$$$, $$$3$$$, $$$3$$$, $$$3$$$

Дальше еще раз прозвучало "3 удара ножом". Все девианты сознались, потому что их стрессы достигли $$$6$$$. Соответственно $$$3 + 3 \ge 5$$$, $$$3 + 3 \ge 4$$$, $$$3 + 3 \ge 6$$$ для второго, третьего и четвертого девиантов.

Так как все сознались, можно вывести меры наказания. Они оказались $$$3$$$, $$$5$$$, $$$4$$$ и $$$6$$$.

Обратите внимание, что пустые строки оставлены лишь для наглядного взаимодействия, их выводить не нужно