Вам задана система труб. Она состоит из двух рядов, каждый из которых состоит из \(n\) труб. Верхняя левая труба имеет координаты \((1, 1)\), а нижняя правая — \((2, n)\).
Всего существует шесть типов труб: два типа прямых труб и четыре типа изогнутых труб. Ниже приведены примеры всех шести типов:
Типы труб Вы можете поворачивать каждую из заданных труб на \(90\) градусов по часовой или против часовой стрелки любое (возможно, нулевое) количество раз (таким образом, типы \(1\) и \(2\) могут переходить друг в друга, а также \(3, 4, 5, 6\) могут переходить друг в друга).
Вы хотите повернуть некоторые трубы таким образом, чтобы поток воды мог начать свое движение в \((1, 0)\) (слева от верхней левой трубы), пойти по трубе в \((1, 1)\), как-то потечь по связным трубам до трубы \((2, n)\) и потечь вправо в \((2, n + 1)\).
Трубы называются связными, если они являются соседними в системе и их концы соединены. Ниже несколько примеров связных труб:
Примеры связных труб Попробуем описать задачу при помощи примера:
Входные данные первого примера И его решение ниже:
Решение первого примера Как вы можете заметить, поток воды — это плохо нарисованная синяя линия. Чтобы достичь ответа, нам необходимо повернуть трубу на позиции \((1, 2)\) на \(90\) градусов по часовой стрелке, трубу на позиции \((2, 3)\) на \(90\) градусов, трубу на позиции \((1, 6)\) на \(90\) градусов, трубу на позиции \((1, 7)\) на \(180\) градусов и трубу на позиции \((2, 7)\) на \(180\) градусов. Тогда поток воды сможет достичь \((2, n + 1)\) из \((1, 0)\).
Вам необходимо ответить на \(q\) независимых запросов.
Выходные данные
Для \(i\)-го запроса выведите ответ на него — «YES» (без кавычек), если возможно повернуть некоторые трубы таким образом, чтобы поток воды смог достичь \((2, n + 1)\) из \((1, 0)\), и «NO» иначе.