D. Сорта кофе (сложная версия)
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия этой задачи. Вы можете найти простую версию в Div. 2 контесте. Обе версии отличаются только в ограничении на количество раз, которое вы можете попросить вашего друга попробовать кофе.

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

Вы собираетесь поехать в другой город, где живет один из ваших друзей. В этом городе $$$n$$$ кафе, где число $$$n$$$ является степенью двойки. В $$$i$$$-м кафе варят кофе сорта $$$a_i$$$.

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

Вы не знаете значений $$$a_1, \ldots, a_n$$$. К счастью, ваш друг хорошо запоминает события последних $$$k$$$ дней, где $$$k$$$ это степень двойки.

Каждый день, вы можете попросить его попробовать чашечку кофе, сваренного в кафе с номером $$$c$$$ и он скажет, пробовал ли он кофе того же сорта в последние $$$k$$$ дней.

Также вы можете попросить его забыть все, что он пробовал до этого. После этого он забудет все предыдущие разы, когда он пробовал кофе. Вы можете делать это не больше $$$30\ 000$$$ раз.

Более формально, память вашего друга это некоторая очередь $$$S$$$. Сделать запрос сходить попробовать кофе в кафе с номером $$$c$$$ означает:

  • Сказать вам, есть ли $$$a_c$$$ в $$$S$$$;
  • Добавить $$$a_c$$$ в конец очереди $$$S$$$;
  • Если $$$|S| > k$$$, удалить первый элемент очереди $$$S$$$.

Запрос забывания всех посещений кафе удаляет все элементы очереди $$$S$$$, то есть отчищает ее.

Вы можете попросить вашего друга попробовать не больше $$$\dfrac{3n^2}{2k}$$$ чашек кофе. Найдите разнообразность города $$$d$$$ (количество различных значений в массиве $$$a$$$).

Обратите внимание, что попросить вашего друга забыть все походы в кафе, что были до этого не считается среди количества запросов попросить вашего друга попробовать кофе.

В некоторых тестах поведение интерактора будет адаптивным. Это означает, что массив $$$a$$$ может быть не фиксированным до начала тестирования вашей программы и может зависеть от ваших запросов. Гарантируется, что в любой момент тестирования, существует хотя бы один массив $$$a$$$, для которого верны все данные до этого ответы на запросы.

Входные данные

В первой строке находится два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n \le 1024$$$, $$$k$$$ и $$$n$$$ это степени двойки).

Гарантируется, что $$$\dfrac{3n^2}{2k} \le 15\ 000$$$.

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

Вы начинаете взаимодействие со считывания двух чисел $$$n$$$ и $$$k$$$.

  • Для того, чтобы попросить вашего друга попробовать чашечку кофе в кафе с номером $$$c$$$, в отдельной строке выведите

    ? $$$c$$$

    Тут $$$c$$$ должно удовлетворять условиям $$$1 \le c \le n$$$. Не забывайте сделать сброс буфера потока вывода после этого.

    В ответ вы получите символ Y (да) или N (нет), сообщающий вам, встречался ли сорт кофе $$$a_c$$$ среди последних $$$k$$$ сортов кофе в памяти вашего друга.

  • Для того чтобы отчистить память вашего друга, в отдельной строке выведите единственный символ R (большая латинская буква). Вы можете сделать этот запрос не более $$$30\ 000$$$ раз.
  • После того, как вы определили количество $$$d$$$ различных сортов кофе, выведите

    ! $$$d$$$

В случае, если запрос, сделанный вами, некорректный или вы сделали больше, чем $$$\frac{3n^2}{2k}$$$ запросов типа ? или больше, чем $$$30\ 000$$$ запросов типа R, в ответ тестирующая программа выведет символ E и закончит тестирование. Вы получите вердикт Wrong Answer. Будьте осторожны, для этого ваша программа должна немедленно завершиться в этом случае, иначе вердикт посылки может быть любым.

После вывода запроса не забывайте переводить строку и делать сброс буфера потока вывода. Иначе, вы получите вердикт Idleness limit exceeded. Для того, чтобы сделать сброс буфера потока вывода, используйте:

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

Взломы

В первой строке теста должно находиться слово fixed

Во второй строке должны содержаться два целых числа $$$n$$$ и $$$k$$$, разделенных пробелом ($$$1 \le k \le n \le 1024$$$, $$$k$$$ и $$$n$$$ это степени двойки).

Должно быть выполнено, что $$$\dfrac{3n^2}{2k} \le 15\ 000$$$.

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

Примеры
Входные данные
4 2
N
N
Y
N
N
N
N
Выходные данные
? 1
? 2
? 3
? 4
R
? 4
? 1
? 2
! 3
Входные данные
8 8
N
N
N
N
Y
Y
Выходные данные
? 2
? 6
? 4
? 5
? 2
? 5
! 6
Примечание

В первом тесте, массив $$$a = [1, 4, 1, 3]$$$. В городе производится $$$3$$$ различных сорта кофе ($$$1$$$, $$$3$$$ и $$$4$$$).

Последовательные сорта кофе, попробованные вашим другом это $$$1, 4, \textbf{1}, 3, 3, 1, 4$$$ (жирным выделены запросы с ответом Y). Обратите внимание, что между двумя запросами ? 4, был запрос отчищения памяти, поэтому ответ на второй запрос ? 4 был N. Если бы этого запроса не было, то ответ на второй запрос ? 4 был бы Y.

Во втором тесте, массив $$$a = [1, 2, 3, 4, 5, 6, 6, 6]$$$. В городе производится $$$6$$$ различных сортов кофе.

Последовательные сорта кофе, попробованные вашим другом это $$$2, 6, 4, 5, \textbf{2}, \textbf{5}$$$.