Уникальные суффиксы (online версия)
У Вас есть изначально пустая строка s. Далее поступает q запросов. Запросы бывают двух типов:
Запрос на добавление символа в конец строки s. Формат запроса имеет вид "+ c", где c — символ, который требуется дописать в конец строки s.
Запрос на проверку уникальности суффикса строки s. Формат запроса имеет вид "? l", где l — длина суффикса текущей строки s, который требуется проверить на уникальность. Суффикс считается уникальным, если он встречается в строке s в качестве подстроки ровно один раз (начиная с позиции |s|-l+1, если считать символы строки один-индексированными).
Ваша задача — после каждого запроса второго типа, вывести "+", если заданный суффикс уникален, или вывести "-" в противном случае.
Входные данные
В первой строке записано единственное целое число q (1 ≤ q ≤ 2·10^6) — количество запросов.
В следующих q строках записаны запросы в формате, описанном в условии задачи. Гарантируется, что все запросы корректны. Гарантируется, что первый запрос имеет первый тип. Гарантируется, что символ c в каждом запросе первого типа является одним из символов "a", "b", "c", "d", "e". Гарантируется, что число l во всех запросах второго типа положительно и не больше текущей длины строки s.
Чтобы немного усложнить задачу, в задаче используется искусственный метод для превращения задачи в задачу online типа. Метод состоит в следующем: каждый раз, когда поступает запрос на добавление символа, если ответ на предыдущий запрос на проверку уникальности суффикса был положительный (то есть, суффикс оказался уникальным), тогда текущий добавляемый символ циклически сдвигается на один вперед. Другими словами, в случае уникальности предыдущего суффикса из запроса вместо символа "a" нужно добавить символ "b"; вместо символа "b" — "c"; вместо символа "d" — "e"; вместо символа "e" — "a". Самый первый запрос не меняется, как и запрос на добавление в случае не уникальности предыдущего суффикса из запроса.
Выходные данные
Выведите ответы на запросы второго типа. Ответы на запросы выводите в порядке появления запросов во входных данных.