птичка находится на верхней строке игрового поля или на крайнем левом столбце, то она остается на месте, а не смещается.<br /> Также Петя обнаружил, что некоторые ячейки игрового поля содержат препятствия, которые птичка должна обходить. Препятствия представляют собой прямоугольные области, занимающие несколько строк и столбцов. При попадании на препятствие птичка должна обойти его, двигаясь по вертикали (выше или ниже), пока не окажется снова в свободной ячейке. При этом Пете нужно управлять движением птички так, чтобы она обошла все препятствия и достигла конечной ячейки игрового поля.</p> <p>Напишите программу, которая будет управлять движением птички по игровому полю. На вход программе подаются размеры игрового поля, начальные координаты птички, конечные координаты ячейки, а также координаты препятствий. Программа должна выводить последовательность действий, которую нужно предпринять Пете для достижения конечной ячейки из начальной.</p> <h3>Формат ввода</h3> <p>В первой строке вводятся два целых числа n и m (1 ≤ n,m ≤ 100) — размеры игрового поля. Во второй строке вводятся два целых числа a и b (1 ≤ a ≤ n, 1 ≤ b ≤ m) — начальные координаты птички. В третьей строке вводятся два целых числа c и d (1 ≤ c ≤ n, 1 ≤ d ≤ m) — конечные координаты ячейки. В четвертой строке вводится одно целое число k (0 ≤ k ≤ n*m) — количество препятствий. Далее вводится k строк, каждая из которых описывает препятствие и содержит четыре целых числа x1,y1,x2,y2 (1 ≤ x1,x2 ≤ n, 1 ≤ y1,y2 ≤ m), где (x1,y1) — координаты верхнего левого угла препятствия, а (x2,y2) — координаты нижнего правого угла препятствия.</p> <h3>Формат вывода</h3> <p>Если существует последовательность действий, которая позволяет достичь конечной ячейки из начальной, то в первой строке выведите "YES". Во второй строке выведите одно целое число k (0 ≤ k ≤ n*m) — количество действий, которое нужно выполнить. Далее выведите k чисел, каждое из которых — это либо -1, либо 0, либо 1:</p> <p>• -1 — если нужно нажать кнопку, • 1 — если нужно нажать кнопку • 0 — если нужно нажать кнопку Цифру -1 нужно выводить, если нужно нажать кнопку.<br /> Цифру 1 нужно выводить, если нужно нажать кнопку<br /> Цифру 0 нужно выводить, если нужно нажать кнопку<br /> Ваш ответ будет считаться правильным, если количество действий в нём не превышает 3*n*m и оно является минимально возможным, то есть если существует другой ответ с меньшим количеством действий, то ваш ответ будет считаться неправильным.</p> <pre><blockquote><strong>Примеры номеров.</strong></blockquote></pre> <h3>Пример 1</h3> <pre><blockquote><strong>Ввод</strong> 5 5 3 1 2 5 3 2 3 4 4 1 1 1 5 3 5 5 5 <strong>Вывод</strong> YES 10 0 0 1 -1 -1 -1 0 0 0 1 </blockquote></pre> <h3>Пример 2</h3> <pre><blockquote><strong>Ввод</strong> 3 3 2 1 3 3 2 2 2 2 3 2 1 2 1 <strong>Вывод</strong> NO</blockquote></pre> <h3>Пример 3</h3> <pre><blockquote><strong>Ввод</strong> 3 3 2 1 3 3 2 1 2 2 2 2 2 3 2 <strong>Вывод</strong> YES 6 -1 -1 -1 -1 1 1 </blockquote></pre> <h2>Описание тестов</h2> <p>В первом примере назначение &quot;пойти во время&quot; одно — сначала нажимаем кнопку, что позволяет пройти препятствие с координатами (2,3) - (4,4), потом поднимаемся две ячейки вверх, ещё семь раз — перемещаемся вправо — и на конечных координатах нажимаем кнопку.<br /> Во втором примере первое препятствие занимает все поле, поэтому даже не числится совершить действие можно, а второе препятствие перекрывает путь до цели.<br /> В третьем примере вплоть до (2,2) сделать ничего нельзя — единственная возможность пройти первое препятствие - нажать кнопку<br /> периодически, но в таком случае невозможно обойти второе препятствие.</p>