eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

(p, q) - кінь

(p, q) - кінь

Ліміт часу 1 секунда
Ліміт використання пам'яті 122 MiB

(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 (1x_1, x_2M100, 1y_1, y_2N100, 0p100, 0q100).

Вихідні дані

Перший рядок вихідного файлу повинен містити ціле число 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.

Приклад

Вхідні дані #1
3 3 1 1 1 1 3 3
Вихідні дані #1
2
1 1
2 2
3 3
Вхідні дані #2
2 2 1 1 1 1 1 2
Вихідні дані #2
-1
Джерело ЛКШ-2011 Севастополь 08.08.2011 д.2 1-ша ліга