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

Лиса дала Коту два целых положительных числа $$$n$$$ и $$$k$$$. У неё есть секретный массив $$$a_1, \ldots, a_n$$$ длины $$$n$$$, такой, что $$$1 \leq a_i \leq n$$$ для каждого $$$i$$$. Она предложила Коту сыграть в следующую игру:

Для любых двух целых чисел $$$l, r$$$ таких, что $$$1 \leq l \leq r \leq n$$$, определим $$$f(l, r) = (r - l + 1) \cdot \max\limits_{x=l}^r a_x$$$. Иными словами, $$$f(l, r)$$$ равно максимуму подмассива $$$a_l, \ldots, a_r$$$, умноженному на его длину.

Кот может задать Лисе не более $$$2 n$$$ вопросов о массиве. За один вопрос он может сообщить ей два целых числа $$$l$$$ и $$$x$$$ ($$$1 \leq l \leq n, 1 \leq x \leq 10^9$$$), а Лиса в качестве ответа назовет одно целое число $$$p$$$ — наименьшее целое положительное число $$$r$$$, такое, что $$$f(l, r) = x$$$, или $$$n+1$$$, если такого $$$r$$$ не существует.

С помощью этих вопросов Коту нужно найти наибольшее значение $$$m$$$, такое, что существует последовательность $$$c_1, \ldots, c_{k-1}$$$ такая, что $$$1 \leq c_1 < \ldots < c_{k-1} < n$$$ и $$$f(1, c_1) = f(c_1 + 1, c_2) = \ldots = f(c_{k-1}+1, n) = m$$$. Если такого $$$m$$$ не существует, он должен указать на это и принять в качестве ответа $$$-1$$$. Заметьте, что для $$$k = 1$$$, $$$m$$$ всегда равен $$$f(1, n)$$$.

Другими словами, найдите наибольшее $$$m$$$, при котором вы сможете разбить массив ровно на $$$k$$$ подмассивов ($$$k$$$ — константа, данная вам в начале взаимодействия) так, чтобы у всех подмассивов результат умножения их длины на максимум был равен $$$m$$$, или определите, что такого $$$m$$$ не существует. Каждый элемент должен принадлежать ровно одному из подмассивов.

Кот не знает, как решить эту задачу, поэтому он попросил ваc помочь ему.

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых положительных числа $$$n$$$ и $$$k$$$ ($$$1 \leq k \leq n \leq 10^4$$$) — длину секретного массива и количество подмассивов в желаемом разбиении.

Далее вы можете делать запросы следующим образом: выведите одну строку вида «$$$\mathtt{?} \ l \ x$$$» (должно выполняться условия $$$1 \leq l \leq n$$$, $$$1 \leq x \leq 10^9$$$), и вы получите наименьшее целое число $$$r$$$ такое, что $$$l \leq r \leq n$$$ и $$$f(l, r) = x$$$, или $$$n + 1$$$, если такого $$$r$$$ не существует.

Если вы хотите вывести ответ, выведите «$$$\mathtt{!} \ m$$$» и получите $$$1$$$ в случае правильного ответа и $$$-1$$$ в противном случае. В первом случае взаимодействие продолжается со следующим набором входных данных. Обратите внимание, что вывод ответа не засчитывается в количество сделанных запросов. Обратите внимание, что значения для следующего набора входных данных вы получите не сразу, сначала вам необходимо прочитать, был ли ваш ответ на последний набор входных данных правильным.

Если в любой момент вы получите целое число $$$-1$$$, это означает, что ваша программа сделала некорректный запрос, превысила лимит запросов или дала неправильный ответ. Чтобы получить вердикт Неправильный ответ, ваша программа должна немедленно завершиться. В противном случае вы можете получить любой вердикт, так как программа продолжит чтение из закрытого потока.

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

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

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^4$$$.

Взломы

Формат взломов должен быть следующим: первая строка должна содержать одно целое число $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — количество наборов входных данных. Далее следует описание наборов.

Первая строка каждого набора входных данных должна содержать два целых числа $$$n$$$ и $$$k$$$ ($$$1 \leq k \leq n \leq 10^4$$$) — длину массива $$$a$$$ и количество подмассивов, на которое вы хотите его разбить.

Вторая строка должна содержать $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n $$$ ($$$1 \leq a_i \leq n $$$).

Сумма $$$n$$$ по всем наборам входных данных не должна превышать $$$10^4$$$.