Сережа любит самые разные алгоритмы. Недавно он придумал новый алгоритм, на вход которому подается строка. Обозначим входную строку алгоритма как q = q1q2... qk. Алгоритм состоит из двух шагов:
- Найти любую непрерывную подпоследовательность (подстроку) из трех символов строки q, которая не равна ни одной из строк «zyx», «xzy», «yxz». Если q не содержит ни одной такой подпоследовательности, завершить алгоритм, иначе перейти к шагу 2.
- Переставить буквы в найденной подпоследовательности случайным образом, перейти к шагу 1.
Сережа считает, что алгоритм корректно работает на строке q, если существует хоть какая-то ненулевая вероятность того, что алгоритм завершится. Если же алгоритм в любом случае будет работать бесконечно долго на строке, считается, что он работает некорректно на ней.
Сережа хочет протестировать свой алгоритм. Для этого у него есть строка s = s1s2... sn, состоящая из n символов. Мальчик проводит серию из m тестов. В качестве i-го теста он подает на вход алгоритму строку slisli + 1... sri (1 ≤ li ≤ ri ≤ n). К сожалению, его реализация алгоритма работает слишком долго, поэтому Сережа обратился к вам за помощью. Для каждого теста (li, ri) определите, отработает алгоритм корректно на этом тесте или нет.
Примечание
В первом тесте в первом и втором тесте алгоритм всегда закончит работу за один шаг. В четвертом запросе можно получить строку «xzyx», на которой алгоритм закончит работу. В остальных запросах алгоритм работает некорректно.