Задача E. Загадочная последовательность ≡

Условие

Данная задача является интерактивной.

Долгое время мальчик Петя коллекционировал целые числа. Сейчас в его коллекции уже N чисел. Разумеется, Петя бережно относится к своей коллекции: не разбрасывает по квартире, и, более того, хранит её отсортированной по неубыванию.

Сегодня Петя решил, что хранить числа в отсортированном виде не так интересно, поэтому он хочет перемешать их и получить новую последовательность.

Неровностью последовательности называется сумма модулей разности почти соседних элементов. Два элемента последовательности являются почти соседними, если их номера отличаются ровно на K. Например, если K = 2, тогда почти соседними элементами являются числа на позициях 1 и 3, 2 и 4, 3 и 5 и т.д.

Петя уже очень хорошо знает математику, поэтому он смог написать формулу для подсчета неровности: ∑N − Ki = 1|a_i − a_i + K|. Теперь Петя хочет узнать минимальное значение неровности, которое можно получить для его коллекции после перестановки элементов. Вы должны ему с этим помочь.

Петя не готов просто так показывать свою коллекцию первому встречному, потому что боится, что её могут украсть. Но чтобы вы всё таки смогли ему помочь, он готов ответить на несколько вопросов касательно своей коллекции. А именно — он может назвать модуль разности между двумя любыми элементами последовательности. Петя может ответить лишь на Q вопросов, после этого он начнёт подозревать вас в попытке скопировать коллекцию.

Пояснение

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

Сначала на вход программе-решению подаётся два целых числа N и K — количество чисел в последовательности и расстояние между почти соседними элементами.

Для каждого теста жюри зафиксировало число Q — максимальное количество вопросов, которые можно задать. Гарантируется, что Q вопросов достаточно, чтобы решить задачу. Это число не сообщается программе-решению. Если решение делает более Q вопросов, то на этом тесте оно получает в качестве результата тестирования "Wrong answer".

Чтобы задать вопрос программа-решение должна вывести строку вида "? i j", где i и j (1 ≤ i, j ≤ N) — целые числа, номера чисел в последовательности. В ответ на вопрос программа жюри подаёт на вход программе-решению значение |a_i − a_j| — модуль разности соответствующих элементов последовательности.

Если программа-решение определила ответ на задачу, она должна вывести строку "! ans", где ans — ответ на задачу. После этого программа-решение должна завершиться.

Гарантируется, что в каждом тесте числа в последовательности не изменяются в зависимости от вопросов программы-решения.

Каждый вопрос и вывод ответа должен заканчиваться символом перевода строки \n, а также необходимо выполнить сброс буфера:

Ограничения

1 ≤ N ≤ 10⁶

1 ≤ K ≤ 10³

1 ≤ a_i ≤ 10⁹

a₁ ≤ a₂ ≤ ...  ≤ a_N − 1 ≤ a_N

Описание подзадач и системы оценивания

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

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

По запросу сообщается результат окончательной проверки на каждом тесте.

Пояснение к примерам

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

Обратите внимание, что первый и второй примеры относятся к первой подзадаче, а третий и четвёртый — ко второй.

В первом примере можно расположить первые четыре числа на четных позициях, а остальные числа — на нечетных.

Во втором примере выгоднее всего не менять расположение чисел.

В третьем примере исходная последовательность может быть следующей: 1 4 5 7 13. Расположить эти числа так, чтобы неровность была минимальна, можно несколькими способами. Например, 1 7 13 4 5. Тогда разница между почти соседними элементами равна: |1 − 4| + |7 − 5| = 3 + 2 = 5.

В четвёртом примере нет ни одной пары почти соседних элементов.

Примеры тестов

8 2

3

0

1

2

Ok

? 1 4

? 4 4

? 5 6

? 6 8

! 6

10 1

8

991

999

Ok

? 1 9

? 9 10

? 1 10

! 999

5 3

3

1

2

6

Ok

? 1 2

? 2 3

? 3 4

? 4 5

! 5

2 3

999999

999999

Ok

? 1 2

? 2 1

! 0