Problems
Уникальные суффиксы
Уникальные суффиксы
У Вас есть изначально пустая строка \textbf{s}. Далее поступает \textbf{q} запросов. Запросы бывают двух типов:
\begin{enumerate}
\item Запрос на добавление символа у конец строки \textbf{s}. Формат запроса имеет вид "\textbf{+ c}", где --- символ, который требуется дописать в конец строки \textbf{s}.
\item Запрос на проверку уникальности суффикса строки \textbf{s}. Формат запроса имеет вид "\textbf{? l}", где \textbf{l} --- длина суффикса текущей строки \textbf{s}, который требуется проверить на уникальность. Суффикс считается уникальным, если он встречается в строке \textbf{s} в качестве подстроки ровно один раз (начиная с позиции \textbf{|s|-l+1}, если считать символы строки один-индексированными).
\end{enumerate}
Ваша задача --- после каждого запроса второго типа, вывести "\textbf{+}", если заданный суффикс уникален, или вывести "\textbf{-}">> в противном случае.
\InputFile
В первой строке записано единственное целое число \textbf{q} (\textbf{1} ≤ \textbf{q} ≤ \textbf{2·10^6}) --- количество запросов.
В следующих \textbf{q} строках записаны запросы в формате, описанном в условии задачи. Гарантируется, что все запросы корректны. Гарантируется, что первый запрос имеет первый тип. Гарантируется, что символ \textbf{c} в каждом запросе первого типа является одним из символов "\textbf{a}", "\textbf{b}", "\textbf{c}", "\textbf{d}", "\textbf{e}". Гарантируется, что число \textbf{l} во всех запросах второго типа положительно и не больше текущей длины строки \textbf{s}.
\OutputFile
Выведите \textbf{q} строк --- ответы на запросы второго типа. Ответы на запросы выводите в порядке появления запросов во входных данных.
Input example #1
13 + a ? 1 + a ? 1 ? 2 + a ? 1 ? 2 ? 3 + b ? 3 ? 1 ? 2
Output example #1
+ - + - - + + + +