B. Три религии
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Во время археологических исследований на Ближнем Востоке вы обнаружили следы трёх древних религий: первой религии, второй религии и третьей религии. Вы собрали информацию о развитии каждого из этих верований, и теперь вы думаете, могут ли последователи каждой религии мирно сосуществовать?

Слово Вселенной — это длинное слово, содержащее только строчные английские символы. В каждый момент времени каждое из религиозных верований может быть описано словом, состоящим из строчных английских символов.

Три религии могут сосуществовать мирно, если их описания являются непересекающимеся подпоследовательностями Слова Вселенной. Формально, религии могут сосуществовать мирно если можно покрасить некоторые символы Слова Вселенной в три цвета: $$$1$$$, $$$2$$$, $$$3$$$, что каждый символ покрашен в не более чем один цвет, и описание $$$i$$$-й религии может быть построено из Слова Вселенной удалением всех символов, которые не покрашены в цвет $$$i$$$.

Однако религии изменяются. Вначале описание каждой религии пусто. Время от времени, в конец описания какой-нибудь из религий добавляется символ или из описания какой-то религии удаляется последний символ. После каждого изменения определите, могут ли три религии сосуществовать мирно.

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

В первой строке записаны два целых числа $$$n, q$$$ ($$$1 \leq n \leq 100\,000$$$, $$$1 \leq q \leq 1000$$$) — длина Слова Вселенной и количество изменений религий, соответственно. В следующей строке содержится Слово Вселенной — строка длины $$$n$$$, состоящая из строчных букв латинского алфавита.

Каждая из следующих строк содержит описание одного изменения в одном из следующих форматов:

  • + $$$i$$$ $$$c$$$ ($$$i \in \{1, 2, 3\}$$$, $$$c \in \{\mathtt{a}, \mathtt{b}, \dots, \mathtt{z}\}$$$: в конец описания $$$i$$$-й религии добавляется символ $$$c$$$.
  • - $$$i$$$ ($$$i \in \{1, 2, 3\}$$$) – из описания $$$i$$$-й религии удаляется последний символ. Гарантируется, что в этот момент описание этой религии непусто.

Гарантируется, что описания каждой религий в любой момент времени состоит из не более чем $$$250$$$ символов.

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

Выведите $$$q$$$ строк. $$$i$$$-я из них должна содержать «YES» если религии могут мирно сосуществовать после $$$i$$$-й эволюции, и «NO» иначе.

Вы можете выводить каждую букву в любом регистре (верхнем или нижнем).

Примеры
Входные данные
6 8
abdabc
+ 1 a
+ 1 d
+ 2 b
+ 2 c
+ 3 a
+ 3 b
+ 1 c
- 2
Выходные данные
YES
YES
YES
YES
YES
YES
NO
YES
Входные данные
6 8
abbaab
+ 1 a
+ 2 a
+ 3 a
+ 1 b
+ 2 b
+ 3 b
- 1
+ 2 z
Выходные данные
YES
YES
YES
YES
YES
NO
YES
NO
Примечание

В первом примере, после 6 изменений описания религий равны: ad, bc, и ab. Следующая иллюстрация показывает, какими подпоследовательностями Слова Вселенной они являются: