0123. (p, q)-Horse

Input file name:	horse.in
Output file name:	horse.out
Time limit:	500 ms
Memory limit:	64 megabytes

(p,q)-horse is a generalisation of chess Knight who moves p steps one direction and q steps another (perpendicular) direction. Ordinary chess Knight is thus a (2,1)-horse.

Your task is to determine how many moves (p,q)-horse needs to go from one cell on M*N chess-board to another.

Input file

One and only line in the input file contains 8 integer numbers M, N, p, q, x₁, y₁, x₂, y₂ (1 ≤ x₁, x₂ ≤ M, 1 ≤ y₁, y₂ ≤ N, 0 ≤ p ≤ M ≤ 100, 0 ≤ q ≤ N ≤ 100).

Output file

First line of the output file must contain an integer number k – number of moves that (p,q)-horse needs to move from cell (x₁,y₁) to the cell (x₂,y₂). k+1 lines must follow, containing sequential positions of (p,q)-horse on the way.

If (p,q)-horse cannot reach (x₂,y₂) from (x₁,y₁), output -1.

Examples:

horse.in	horse.out
3 3 1 1 1 1 3 3	2 1 1 2 2 3 3
2 2 1 1 1 1 1 2	-1

Source: Petrozavodsk Summer 2003. Blitz Kontest, Monday, August 25
Author: Andrew Lopatin, Nick Durov

Discuss       Submit a solution



Printable version