Это интерактивная задача.
Ayush придумал еще один способ задать пароль для своего замка. В замке есть \(n\) слотов, в каждом слоте может находится любое неотрицательное целое число. Пароль \(P\) это последовательность из \(n\) целых чисел, \(i\)-й из которых соответствует \(i\)-му слоту замка.
Чтобы задать пароль, Ayush придумал последовательность \(A\) из \(n\) целых чисел из отрезка \([0, 2^{63}-1]\). Затем, он определил \(i\)-й элемент \(P\) как побитовое ИЛИ всех чисел в массиве кроме \(A_i\).
Вам нужно отгадать пароль. Чтобы задать запрос, вы можете выбрать непустое подмножество индексов массива и спросить побитовое ИЛИ всех элементов массива с индексами в этом подмножестве. Вы можете задать не более 13 запросов.
Протокол взаимодействия
Чтобы задать вопрос, в отдельной строке:
- Сначала выведите «? c» (без кавычек), где \(c\) \((1 \leq c \leq n)\) обозначает размер подмножества запроса, после чего выведите \(c\) различных целых чисел из отрезка \([1, n]\), разделенных пробелами.
В ответ на каждый запрос, вы получите число \(x\) — побитовое ИЛИ чисел с выбранными индексами. Если вы спросили некорректное множество индексом или вы превысили количество запросов, тогда вы получите \(x = -1\). В таком случае вы должны немедленно завершить выполнение программы.
Если вы угадали пароль, в отдельной строке выведите «!» (без кавычек), после чего выведите \(n\) целых чисел, разделенных пробелами — последовательность-пароль.
Отгадывание пароля не считается в числе загаданных запросов.
Интерактор не адаптивный. Массив \(A\) не меняется с запросами.
После вывода запроса, не забывайте выводить конец строки и сбрасывать поток вывода. Иначе, вы получите верикт Превышен лимит бездействия. Чтобы сделать это, используйте:
- fflush(stdout) или cout.flush() в C++;
- System.out.flush() в Java;
- flush(output) в Pascal;
- stdout.flush() в Python;
- читайте документацию для остальных языков.
Взломы
Чтобы взломать решение, используйте следующий формат:
В первой строке, выведите одно целое число \(n\) \((2 \le n \le 1000)\) — количество слотов в замке. Во второй строке выведите \(n\) целых чисел из отрезка \([0, 2^{63} - 1]\), разделенных пробелами — массив \(A\).
Примечание
Массив \(A\) в примере это \(\{{1, 2, 4\}}\). Первый элемент пароля это побитовое ИЛИ элементов \(A_2\) и \(A_3\), второй элемент это побитовое ИЛИ элементов \(A_1\) и \(A_3\), а третий элемент это побитовое ИЛИ элементов \(A_1\) и \(A_2\). Таким образом, пароль равен \(\{{6, 5, 3\}}\).