Автор: | Евгений Татаринов | Ограничение времени: | 1 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 128 Мб | |
Выходной файл: | Стандартный выход | |||
Максимальный балл: | 100 |
Дежавю — феномен, при котором у человека возникает ощущение, что он уже испытывал определенную последовательность событий в прошлом. Часто вы можете ощущать подобное в преддверии крупных семейных праздников, например Нового Года.
В течении предновогоднего дня с Анжеликой произошло какое-то количество событий (для удобства будем нумеровать события от 1 до 106, то есть существует 106 различных событий). После каких-то событий Анжелика испытала чувство дежавю, то есть, Анжелика думает, что последовательность из последних K событий уже встречалась среди событий, которые были раньше последних K событий. Для каждого раза сообщите, ложное ли это чувство или нет.
В первой строке вводится натуральное число K.
Во всех следующих строках вводится по одному из трех запросов следующего вида:
e X
— произошло событие под номером X (1 ≤ X ≤ 106)dejavu
— Анжелика испытала чувство дежавю. Для каждого такого запроса надо вывести false
, если чувство ложное, иначе выведите true
. Гарантируется, что получая данный запрос, произошло хотя бы 2K событий.stop
— самый последний запрос, который показывает, что день закончился. После этого запроса ничего больше не происходит.Гарантируется, что общее количество запросов Q не превзойдет 105.
Для каждого запроса второго вида на новой строке выведите false
, если чувство ложное, иначе выведите true
.
1 ≤ K ≤ 104, 1 ≤ X ≤ 106
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.
Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.
По запросу сообщается результат окончательной проверки на каждом тесте.
Подзадача | Баллы | Дополнительные ограничения | |
---|---|---|---|
1 | 10 | 1 ≤ Q ≤ 103 | |
2 | 35 | 1 ≤ Q ≤ 104 | |
2 | 55 | 1 ≤ Q ≤ 105 |
Первый эффект дежавю. Последовательность событий: (1, 2, 1, 2). Последние 2 события: (1, 2). Оставшиеся события: (1, 2). Последовательность (1, 2) встречается в последовательности (1, 2).
Второй эффект дежавю. Последовательность событий: (1, 2, 1, 2, 2). Последние 2 события: (2, 2). Оставшиеся события: (1, 2, 1). Последовательность (2, 2) не встречается в последовательности (1, 2, 1).
Третий эффект дежавю. Последовательность событий: (1, 2, 1, 2, 2, 2). Последние 2 события: (2, 2). Оставшиеся события: (1, 2, 1, 2). Последовательность (2, 2) не встречается в последовательности (1, 2, 1, 2).
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|