Это сложная версия этой задачи. Вы можете найти простую версию в 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$$$.

• Для того, чтобы попросить вашего друга попробовать чашечку кофе в кафе с номером $$$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$$$).