Сережа любит самые разные алгоритмы. Недавно он придумал новый алгоритм, на вход которому подается строка. Обозначим входную строку алгоритма как q = q₁q₂... q_k. Алгоритм состоит из двух шагов:

1. Найти любую непрерывную подпоследовательность (подстроку) из трех символов строки q, которая не равна ни одной из строк «zyx», «xzy», «yxz». Если q не содержит ни одной такой подпоследовательности, завершить алгоритм, иначе перейти к шагу 2.
2. Переставить буквы в найденной подпоследовательности случайным образом, перейти к шагу 1.

Сережа считает, что алгоритм корректно работает на строке q, если существует хоть какая-то ненулевая вероятность того, что алгоритм завершится. Если же алгоритм в любом случае будет работать бесконечно долго на строке, считается, что он работает некорректно на ней.

Сережа хочет протестировать свой алгоритм. Для этого у него есть строка s = s₁s₂... s_n, состоящая из n символов. Мальчик проводит серию из m тестов. В качестве i-го теста он подает на вход алгоритму строку s_lis_li + 1... s_ri (1 ≤ l_i ≤ r_i ≤ n). К сожалению, его реализация алгоритма работает слишком долго, поэтому Сережа обратился к вам за помощью. Для каждого теста (l_i, r_i) определите, отработает алгоритм корректно на этом тесте или нет.