Задача . F. Сорта кофе (простая версия)

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

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

Вы собираетесь поехать в другой город, где живет один из ваших друзей. В этом городе \(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{2n^2}{k}\) чашек кофе. Найдите разнообразность города \(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{2n^2}{k}\) запросов типа ? или больше, чем \(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{2n^2}{k} \le 20\ 000\).

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