У Вас есть строка \textbf{s}, которая может содержать строчные латинские буквы ('\textbf{a}', '\textbf{b}', ..., '\textbf{z}'). Изначально она пустая. На вход поступают запросы трёх типов, которые необходимо последовательно обработать: \begin{enumerate} \item \textbf{i k a}, где \textbf{k} - целое число от \textbf{0} до текущей длины строки \textbf{s}, \textbf{a} - строчная латинская буква. По этому запросу необходимо вставить символ \textbf{a} в строку \textbf{s} помле \textbf{k}-го по счёту её символа. \item \textbf{d k}, где \textbf{k} - целое число от \textbf{1} до текущей длины строки \textbf{s}. По этому запросу необходимо удалить \textbf{k}-й по счёту символ из строки \textbf{s}. \item \textbf{q t}, где \textbf{t} - строка из строчных латинских букв. По этому запросу необходимо определить, является ли строка \textbf{t} подпоследовательность строки \textbf{s} (то есть может ли \textbf{t} быть получена из \textbf{s} пут м удаления из неё некоторого (возможно нулевого) количества символов). В случае положительного ответа - вывести \textbf{1}, в случае отрицательного - \textbf{0}. \end{enumerate} \InputFile Каждая строка входного файла определяет некоторый запрос в виде, укзанном выше. Общее количество запросов не превышает \textbf{10^6}. Общая длина файла не превышает \textbf{4·10^6}. \OutputFile В выходной файл необходимо вывести ответы на все запросы третьего типа в порядке их поступления. Каждый ответ должен находится в отдельной строке.