(p, q)-лошадь - это обобщение обычного шахматного коня. (p, q)-лошадь своим ходом перемещается на p клеток в одном направлении, и на q - в другом (перпендикулярном). Например, (3, 4)-лошадь может переместиться с клетки (5, 6) на клетки (1, 3), (2, 2), (2, 10), (1, 9), (8, 10), (9, 9), (8, 2) и (9, 3). Очевидно, что обычный шахматный конь - это (2, 1)-лошадь.
Ваша задача - определить минимальное число ходов, которое требуется (p, q)-лошади, чтобы добраться от одной клетки шахматной доски M×N до другой. За пределы доски выходить запрещается.
Одна строка содержит 8 целых чисел m, n, p, q, x_1, y_1, x_2, y_2 (1 ≤ x_1, x_2 ≤ m ≤ 100, 1 ≤ y_1, y_2 ≤ n ≤ 100, 0 ≤ p ≤ 100, 0 ≤ q ≤ 100).
Первая строка должна содержать число ходов k, которое требуется (p, q)-лошади, чтобы добраться из клетки (x_1, y_1) в клетку (x_2, y_2). Далее должна следовать k + 1 строка, содержащая последовательные положения (p, q)-лошади на этом пути.
Если (p, q)-лошадь не может добраться из (x_1, y_1) в (x_2, y_2), выведите -1.