Уникальные суффиксы
У Вас есть изначально пустая строка 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.
Выходные данные
Выведите q строк — ответы на запросы второго типа. Ответы на запросы выводите в порядке появления запросов во входных данных.