Под влиянием праздничной атмосферы Сайтама подарил Геносу два клеточных пути длины n (странненький подарок, даже для Сайтамы). Клеточный путь — это упорядоченная последовательность соседних клеток на бесконечной сетке. Две клетки называются соседними, если у них есть общая сторона.
Например, клеточный путь может выглядеть так: (0, 0) → (0, 1) → (0, 2) → (1, 2) → (1, 1) → (0, 1) → ( - 1, 1). Обратите внимание, что клетки в этой последовательности могут повторяться, то есть путь может иметь самопересечения.
Перемещение вдоль пути разрешено только в соседние клетки пути. Таким образом, из i-й позиции можно перейти только в (i - 1)-ю или (i + 1)-ю клетки. Обратите внимание, что из первой и последней ячеек клетчатого пути есть только один возможный ход. Дополнительно обратите внимание, что даже если j-я клетка пути совпадает с i-й, то всё равно можно произвести ходы только в (i - 1)-ю и (i + 1)-ю клетки. Например, из второй клетки приведённого выше пути можно пойти только в первую и третью клетки.
Чтобы перемещение всегда определялось однозначно, в каждом из путей никогда не имеют повторяется одна и та же клетка на отрезке длины три. Например, в правильном клеточном пути не может быть подотрезка вида (0, 0) → (0, 1) → (0, 0)
На первую клетку каждого клеточного пути кладётся по камушку. Генос хочет, чтобы оба камушка докатились до последней ячейки каждого клеточного пути, но всё не так просто. Каждый раз, когда Генос двигает один из камушков, второй камушек копирует его движение, если это возможно. Например, если один камушек движется на восток, то тогда другой камушек постарается тоже двигаться на восток. Под постарается имеется в виду, что если движение на восток возможно, то камушек сделает такое перемещение.
Движение на север соответствует увеличению второй координаты на 1, а движение на юг — её уменьшению на 1. Аналогично движение на восток увеличивает первую координату на 1, а движение на запад уменьшает её на 1.
Даны два правильных клеточных пути. Генос хочет знать, существует ли такая последовательность перемещений, что в итоге оба камушка окажутся в концах своих путей.