Задача D. Дежавю

Автор:Евгений Татаринов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:128 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Дежавю — феномен, при котором у человека возникает ощущение, что он уже испытывал определенную последовательность событий в прошлом. Часто вы можете ощущать подобное в преддверии крупных семейных праздников, например Нового Года.

В течении предновогоднего дня с Анжеликой произошло какое-то количество событий (для удобства будем нумеровать события от 1 до 106, то есть существует 106 различных событий). После каких-то событий Анжелика испытала чувство дежавю, то есть, Анжелика думает, что последовательность из последних K событий уже встречалась среди событий, которые были раньше последних K событий. Для каждого раза сообщите, ложное ли это чувство или нет.

Формат входных данных

В первой строке вводится натуральное число K.

Во всех следующих строках вводится по одному из трех запросов следующего вида:

  1. e X — произошло событие под номером X (1 ≤ X ≤ 106)
  2. dejavu — Анжелика испытала чувство дежавю. Для каждого такого запроса надо вывести false, если чувство ложное, иначе выведите true. Гарантируется, что получая данный запрос, произошло хотя бы 2K событий.
  3. stop — самый последний запрос, который показывает, что день закончился. После этого запроса ничего больше не происходит.

Гарантируется, что общее количество запросов Q не превзойдет 105.

Формат выходных данных

Для каждого запроса второго вида на новой строке выведите false, если чувство ложное, иначе выведите true.

Ограничения

1 ≤ K ≤ 104, 1 ≤ X ≤ 106

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.

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

По запросу сообщается результат окончательной проверки на каждом тесте.

Подзадача Баллы Дополнительные ограничения
1101 ≤ Q ≤ 103
2351 ≤ Q ≤ 104
2551 ≤ 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
2
e 1
e 2
e 1
e 2
dejavu
e 2
dejavu
e 2
dejavu
stop
true 
false 
false 

0.088s 0.016s 13