Это интерактивная задача.
Мы загадали массив \(a\) из \(n\) попарно различных чисел (это значит, что нет одинаковых чисел). Вы можете узнавать информацию об этом массиве с помощью нового прибора, который вы заказали на Amazon.
Данный прибор может отвечать на запрос следующего вида: в ответ на индексы \(k\) различных элементов массива, он вернет вам позицию и значение \(m\)-го по возрастанию среди них.
К сожалению, инструкция к прибору потерялась при доставке. Вы помните \(k\), но не помните \(m\). Ваша задача — найти \(m\) с помощью запросов к данному прибору.
Вы можете задать не более \(n\) запросов.
Обратите внимание, что массив \(a\), а также число \(m\) зафиксированы перед началом взаимодействия и не зависят от ваших запросов. Иными словами, интерактор не адаптивен.
Заметьте, что число запросов минимизировать не нужно, как и угадывать весь массив \(a\). Вам нужно только угадать \(m\).
Протокол взаимодействия
Вы начинаете взаимодействие, считав \(n\) и \(k\).
Чтобы задать вопрос об элементах на позициях \(x_1, x_2, \dots, x_k\), в отдельной строке выведите
\(?\) \(x_1\) \(x_2\) \(x_3\) ... \(x_k\)
Числа в запросе должны удовлетворять условию \(1 \le x_i \le n\), и все \(x_i\) должны быть различными. Не забудьте сделать операцию 'flush', чтобы получить ответ.
В ответ, вы получите два числа \(pos\) и \(a_{pos}\) — позиция в массиве \(a\) \(m\)-го в порядке возрастания элемента среди \(a_{x_1}, a_{x_2}, \dots, a_{x_k}\), и сам элемент на этой позиции.
В случае, если ваш запрос не соответствует требованиям, или вы задали более \(n\) запросов, программа выведет \(-1\) и прекратит взаимодействие. Вы получите вердикт Неправильный ответ. Вам нужно завершить работу вашей программы, чтобы не получить другие вердикты.
Когда вы определили \(m\), выведите
\(!\) \(m\)
После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
- fflush(stdout) или cout.flush() в C++;
- System.out.flush() в Java;
- flush(output) в Pascal;
- stdout.flush() в Python;
- смотрите документацию для других языков.
Формат взломов
Для взломов используйте следующий формат:
Первая строка должна содержать три целых числа \(n, k, m\) (\(1 \le m \le k < n \le 500\)) — длина массива, количество чисел в запросе, и какое в порядке возрастания число возвращает прибор.
В следующей строке выведите \(n\) целых чисел \(a_1, a_2, \dots, a_n\) (\(0\le a_i \le 10^9\)) — элементы массива. Они должны быть попарно различными.
Примечание
В примере, \(n = 4\), \(k = 3\), \(m = 3\), \(a = [2, 0, 1, 9]\).