Проверка на подпоследовательность

У Вас есть строка s, которая может содержать строчные латинские буквы ('a', 'b', ..., 'z'). Изначально она пустая. На вход поступают запросы трёх типов, которые необходимо последовательно обработать:

1. i k a, где k - целое число от 0 до текущей длины строки s, a - строчная латинская буква. По этому запросу необходимо вставить символ a в строку s помле k-го по счёту её символа.

2. d k, где k - целое число от 1 до текущей длины строки s. По этому запросу необходимо удалить k-й по счёту символ из строки s.

3. q t, где t - строка из строчных латинских букв. По этому запросу необходимо определить, является ли строка t подпоследовательность строки s (то есть может ли t быть получена из s пут м удаления из неё некоторого (возможно нулевого) количества символов). В случае положительного ответа - вывести 1, в случае отрицательного - 0.

Входные данные

Каждая строка входного файла определяет некоторый запрос в виде, укзанном выше. Общее количество запросов не превышает 10^6. Общая длина файла не превышает 4·10^6.

Выходные данные

В выходной файл необходимо вывести ответы на все запросы третьего типа в порядке их поступления. Каждый ответ должен находится в отдельной строке.

Примеры