E. Платиновый треугольник?
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Made in Heaven — довольно любопытный стенд. Конечно, это (возможно) самый сильный Стенд из всех существующих, но он также является ярым любителем головоломок. Например, недавно он задал Qtaro следующую задачу:

Made in Heaven имеет $$$n$$$ скрытых целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$3 \le n \le 5000$$$, $$$1 \le a_i \le 4$$$). Qtaro должен определить все $$$a_i$$$, задав Made in Heaven несколько вопросов следующего вида:

  • В одном запросе Qtaro разрешается дать Made in Heaven три различных индекса $$$i$$$, $$$j$$$ и $$$k$$$ ($$$1 \leq i, j, k \leq n$$$).
  • Если $$$a_i, a_j, a_k$$$ образуют стороны невырожденного треугольника $$$^\dagger$$$, Made in Heaven выдаст площадь этого треугольника.
  • В противном случае, Made in Heaven ответит $$$0$$$.

Задав не более $$$5500$$$ таких вопросов, Qtaro должен либо сказать Made in Heaven все значения $$$a_i$$$, либо сообщить, что нет возможности однозначно определить их.

К сожалению, из-за перезагрузки вселенной, Qtaro не так умен, как Jotaro. Пожалуйста, помогите Qtaro решить задачу Made In Heaven.

——————————————————————

$$$^\dagger$$$ Три целых положительных числа $$$a, b, c$$$ образуют стороны невырожденного треугольника тогда и только тогда, когда выполняются все следующие три неравенства:

  • $$$a+b > c$$$,
  • $$$b+c > a$$$,
  • $$$c+a > b$$$.
Протокол взаимодействия

Взаимодействие начинается с чтения $$$n$$$ ($$$3 \le n \le 5000$$$) — количества скрытых целых чисел.

Чтобы задать вопрос, соответствующий тройке $$$(i, j, k)$$$ ($$$1 \leq i < j < k \leq n$$$), выведите «? $$$i$$$ $$$j$$$ $$$k$$$» без кавычек. После этого вы должны прочитать одно целое число $$$s$$$.

  • Если $$$s = 0$$$, то $$$a_i$$$, $$$a_j$$$ и $$$a_k$$$ не являются сторонами невырожденного треугольника.
  • Иначе, $$$s = 16 \Delta^2$$$, где $$$\Delta$$$ — площадь треугольника. Площадь предоставляется в таком формате для удобства, чтобы вам нужно было вводить только целые числа.

Если числа $$$a_i$$$ не могут быть однозначно определены, выведите «! $$$-1$$$» без кавычек. Иначе, если вы определили все значения $$$a_i$$$, выведите «! $$$a_1$$$ $$$a_2$$$ $$$\dots$$$ $$$a_n$$$» в одну строку.

Интерактор неадаптивный. Скрытый массив $$$a_1, a_2, \dots, a_n$$$ фиксируется заранее и не изменяется в процессе взаимодействия.

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

  • fflush(stdout) или cout.flush() в C++;
  • System.out.flush() в Java;
  • flush(output) в Pascal;
  • stdout.flush() в Python;
  • смотрите документацию для других языков.

Взломы

Для взлома используйте следующий формат.

Первая строка содержат одно целое число $$$n$$$ ($$$3 \le n \le 5000$$$)  – количество скрытых целых чисел.

Вторая строка содержат $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 4$$$)  – скрытый массив.

Примеры
Входные данные
3

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

? 1 2 3

! -1
Входные данные
6

0

0

0

63

15

135
Выходные данные
? 1 2 3

? 2 3 4

? 4 5 6

? 1 5 6

? 3 5 6

? 1 2 4

! 3 2 1 4 2 2
Входные данные

15

3

3

3

3

3

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


? 1 2 3

? 4 6 7

? 8 9 10

? 11 12 13

? 13 14 15

? 4 5 6

! -1
Входные данные

15

3

15

0

3

3

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


? 1 2 3

? 3 4 5

? 4 5 6

? 7 8 9

? 10 11 12

? 13 14 15

! 1 1 1 2 2 4 1 1 1 1 1 1 1 1 1 1
Входные данные

10

3

48

3

48

63

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

? 1 3 5

? 4 6 8

? 1 5 9

? 6 8 10

? 4 2 6

? 7 10 8

! 1 3 1 2 1 2 4 2 1 2
Примечание

В первом примере процесс взаимодействия происходит следующим образом:

StdinStdoutОбъяснение
3Прочитаем $$$n = 3$$$. Существует $$$3$$$ скрытых целых чисел
? 1 2 3Попросим найти площадь, образованную $$$a_1$$$, $$$a_2$$$ и $$$a_3$$$
63Получено $$$16\Delta^2 = 63$$$. Значит, площадь $$$\Delta = \sqrt{\frac{63}{16}} \approx 1.984313$$$
! -1Ответим, что не существует однозначного массива, удовлетворяющего запросам.

Из полученной площади можно сделать вывод, что числа, образующие треугольник, либо ($$$4$$$, $$$4$$$, $$$1$$$), либо ($$$3$$$, $$$2$$$, $$$2$$$) (в определенном порядке). Поскольку существует несколько массивов чисел, удовлетворяющих запросам, уникальный ответ не может быть найден.

Во втором примере процесс взаимодействия происходит следующим образом:

ШагStdinStdoutОбъяснение
16Прочитаем $$$n = 6$$$. Значит, есть $$$6$$$ скрытых чисел
2? 1 2 3Спросим площадь треугольника, образованного $$$a_1$$$, $$$a_2$$$ и $$$a_3$$$
30Они не образуют невырожденный треугольник
4? 2 3 4Спросим площадь треугольника, образованного $$$a_2$$$, $$$a_3$$$ и $$$a_4$$$
50Они не образуют невырожденный треугольник
6? 4 5 6Спросим площадь треугольника, образованного $$$a_4$$$, $$$a_5$$$ и $$$a_6$$$
70Они не образуют невырожденный треугольник
8? 1 5 6Спросим площадь треугольника, образованного $$$a_1$$$, $$$a_5$$$ и $$$a_6$$$
963Получим $$$16\Delta^2 = 63$$$. Тогда площадь $$$\Delta = \sqrt{\frac{63}{16}} \approx 1.984313$$$
10? 3 5 6Спросим площадь треугольника, образованного $$$a_3$$$, $$$a_5$$$ и $$$a_6$$$
1115Получим $$$16\Delta^2 = 15$$$. Тогда площадь $$$\Delta = \sqrt{\frac{15}{16}} \approx 0.968245$$$
12? 1 2 4Спросим площадь треугольника, образованного $$$a_3$$$, $$$a_5$$$ и $$$a_6$$$
13135Получим $$$16\Delta^2 = 135$$$. Тогда площадь $$$\Delta = \sqrt{\frac{135}{16}} \approx 2.904738$$$
14! 3 2 1 4 2 2Однозначный ответ найден, и он равен $$$a = [3, 2, 1, 4, 2, 2]$$$.

Из шагов $$$10$$$ и $$$11$$$ мы можем сделать вывод, что мультимножество $$$\left\{a_3, a_5, a_6\right\}$$$ должно равняться $$$\left\{2, 2, 1\right\}$$$.

Из шагов $$$8$$$ и $$$9$$$, мультимножество $$$\left\{a_1, a_5, a_6\right\}$$$ должно быть либо $$$\left\{4, 4, 1\right\}$$$, либо $$$\left\{3, 2, 2\right\}$$$.

Так как $$$\left\{a_3, a_5, a_6\right\}$$$ и $$$\left\{a_1, a_5, a_6\right\}$$$ пересекаются по $$$a_5$$$ и $$$a_6$$$, делаем вывод, что $$$a_5 = a_6 = 2$$$, а также $$$a_1 = 3$$$, $$$a_3 = 1$$$.

Из шагов $$$6$$$ и $$$7$$$ известно, что $$$a_5 = a_6 = 2$$$, а $$$a_4$$$, $$$a_5$$$ и $$$a_6$$$ не могут образовать невырожденный треугольник, следовательно, $$$a_4 = 4$$$.

При всей известной информации, только $$$a_2 = 2$$$ удовлетворяет запросам, сделанным на шагах $$$2$$$, $$$3$$$, $$$4$$$, $$$5$$$, $$$12$$$ и $$$13$$$.

В третьем примере один массив, удовлетворяющий запросам, — $$$[1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]$$$.