Во время археологических исследований на Ближнем Востоке вы обнаружили следы трёх древних религий: первой религии, второй религии и третьей религии. Вы собрали информацию о развитии каждого из этих верований, и теперь вы думаете, могут ли последователи каждой религии мирно сосуществовать?
Слово Вселенной — это длинное слово, содержащее только строчные английские символы. В каждый момент времени каждое из религиозных верований может быть описано словом, состоящим из строчных английских символов.
Три религии могут сосуществовать мирно, если их описания являются непересекающимеся подпоследовательностями Слова Вселенной. Формально, религии могут сосуществовать мирно если можно покрасить некоторые символы Слова Вселенной в три цвета: \(1\), \(2\), \(3\), что каждый символ покрашен в не более чем один цвет, и описание \(i\)-й религии может быть построено из Слова Вселенной удалением всех символов, которые не покрашены в цвет \(i\).
Однако религии изменяются. Вначале описание каждой религии пусто. Время от времени, в конец описания какой-нибудь из религий добавляется символ или из описания какой-то религии удаляется последний символ. После каждого изменения определите, могут ли три религии сосуществовать мирно.
Выходные данные
Выведите \(q\) строк. \(i\)-я из них должна содержать «YES» если религии могут мирно сосуществовать после \(i\)-й эволюции, и «NO» иначе.
Вы можете выводить каждую букву в любом регистре (верхнем или нижнем).
Примечание
В первом примере, после 6 изменений описания религий равны: ad, bc, и ab. Следующая иллюстрация показывает, какими подпоследовательностями Слова Вселенной они являются:
