Известно, что характер шахматной позиции во многом определяется положением пешек - наиболее стабильных фигур. Вам предлагается два положения пешек. Вашей программе необходимо определить, могло ли второе положение произойти из первого при возможных взятиях фигур (то есть пешки могли ходить вперед и брать фигуры (не пешки) - вперед-вправо и вперед-влево на одну клетку по диагонали).
Количество и белых (М) и черных (N) пешек в начальной и конечной позициях одинаково. Фигуры на позициях не указываются, но считается, что их достаточно, чтобы осуществить любую последовательность взятий.
Программа должна обработать несколько примеров задачи, каждый из которых описывается отдельным блоком входных данных.
Входные данные
Входной файл INPUT.TXT состоит из блоков данных, каждый из которых задаёт пару "начальная - конечная позиции". В первой строке - количество блоков.
Далее идут блоки данных. Первая строка блока содержит числа М и N (1 Ј M, N Ј 8). Затем в М строках содержатся координаты белых пешек начальной позиции, записанные через пробел. Далее в N строках - координаты чёрных пешек начальной позиции. В последующих М и N строках - координаты белых и черных пешек (соответственно) конечной позиции. Координаты задаются двумя числами - номером вертикали и номером горизонтали. Имейте в виду, что белые пешки двигаются вперед с возрастанием номера горизонтали (от 2-ой до 8-ой горизонтали), а чёрные - с убыванием (от 7-ой до 1-ой).
Выходные данные
Выходной файл OUTPUT.TXT должен состоять из строк, количество которых равно количеству блоков. В каждой строке - одно число, определяющее решение для соответствующего блока: 1 - если конечная позиция могла получиться из первой, 0 - если не могла.
| Пример INPUT.TXT: | OUTPUT.TXT для примера: |
| 2 | 1 |
| 1 1 | 0 |
| 1 2 | |
| 1 7 | |
| 1 7 | |
| 1 2 | |
| 1 1 | |
| 2 2 | |
| 7 7 | |
| 7 7 | |
| 2 2 |
Ограничение времени: 1 сек на тест