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

Это сложная версия задачи. Отличия от простой версии состоят в том, что в сложной версии $$$1 \le t \le \min(n, 10^4)$$$ и количество запросов ограничено числом $$$6 \cdot 10^4$$$.

Поликарп играет в компьютерную игру. В этой игре загадан массив, состоящий из нулей и единиц. Поликарп выиграет, если $$$t$$$ раз угадает позицию $$$k$$$-го слева нуля.

Поликарп может сделать не более $$$6 \cdot 10^4$$$ запросов следующего вида:

• ? $$$l$$$ $$$r$$$ — узнать сумму всех элементов на позициях от $$$l$$$ до $$$r$$$ ($$$1 \le l \le r \le n$$$) включительно.

Чтобы игра была более интересной, каждый угаданный ноль превращается в единицу и игра продолжается на измененном массиве. Более формально, если позиция $$$k$$$-го нуля равнялась $$$x$$$, тогда после того, как Поликарп угадает эту позицию, $$$x$$$-й элемент массива заменится с $$$0$$$ на $$$1$$$.

Помогите Поликарпу выиграть в игре.

Сначала ваша программа должна считать два целых числа $$$n$$$ и $$$t$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le t \le \min(n, 10^4)$$$).

Далее следуют $$$t$$$ строк, каждая из которых содержит одно целое число $$$k$$$ ($$$1 \le k \le n$$$). Гарантируется, что в момент запроса в массиве есть хотя бы $$$k$$$ нулей. Для того, чтобы получить следующее значение $$$k$$$, вы должны вывести ответ для текущего значения $$$k$$$.

После этого вы можете сделать не более $$$6 \cdot 10^4$$$ запросов.

Используйте следующий формат, чтобы вывести ответ (это не считается за запрос, то есть не учитывается в ограничении $$$6 \cdot 10^4$$$):

• ! $$$x$$$ — позиция $$$k$$$-го нуля.

Позиции в массиве нумеруются слева направо от $$$1$$$ до $$$n$$$ включительно.

После вывода $$$t$$$ ответов ваша программа должна немедленно завершиться.

В этой задаче интерактор не адаптивный. Это означает, что в рамках одного теста загаданный массив и запросы не меняются.

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

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

Ваше решение может получить вердикт Решение «зависло», если вы ничего не выведете или забудете сбросить буфер вывода.

Чтобы сбросить буфер вывода вам нужно сделать следующее сразу после вывода запроса и символа конца строки:

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

Взломы

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

В первой строке выведите строку $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$), состоящую из нулей и единиц, и целое число $$$t$$$ ($$$1 \le t \le \min(|s|, 10^4)$$$) — загаданный массив и количество запросов, соответственно. В следующих $$$t$$$ строках выведите число $$$k$$$ ($$$1 \le k \le |s|$$$).

Взламываемое решение не будет иметь прямого доступа к загаданному массиву.