Задача Спасение коня

Описание

Путешествуя по Стране чудес, Алиса случайно наткнулась на (p, q)-коня. Зная, к чему приводят встречи в чистом поле с незнакомыми одинокими девочками, (p, q)-конь дал стрекача. Поле, по которому бежит Конь, имеет вид шахматной доски M × N клеток (1 <= N,M <= 100). Чтобы убежать, Конь должен переместиться из позиции (x1, y1), где он встретился с Алисой, в позицию (x2, y2). За один ход (p, q)-конь перемещается на p клеток в одном направлении и на q в другом (перпендикулярном). Обычный шахматный конь, например, является (2, 1)-конем.

Определить минимально возможное число ходов для спасения Коня.

Формат входных данных

Первая и единственная строка входного файла содержит 8 целых чисел M, N, p, q, x1, y1, x2, y2 (1 <= x1, x2 <= M, 1 <= y1, y2 <= N, 0 <= p <= M <= 100, 0 <= q <= N <= 100).

Формат выходных данных

Первая строка выходного файла должна содержать целое число K – минимальное число ходов, которое потребуется Коню, чтобы убежать. В следующих K + 1 строках выведите последовательно координаты всех клеток спасительного маршрута. В случае, если искомого маршрута нет, выведите в выходной файл единственное число −1.