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

Условие

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ K ≤ 10⁴, 1 ≤ X ≤ 10⁶

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

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

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

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

Пояснение к примеру

Первый эффект дежавю. Последовательность событий: (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).

Примеры тестов

2
e 1
e 2
e 1
e 2
dejavu
e 2
dejavu
e 2
dejavu
stop

true 
false 
false