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, x1, y1, x2, y2 (1 ≤ x1, x2 ≤ M, 1 ≤ y1, y2 ≤ 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 (x1,y1) to the cell (x2,y2). k+1 lines must follow, containing sequential positions of (p,q)-horse on the way.

If (p,q)-horse cannot reach (x2,y2) from (x1,y1), output -1.

Examples:

horse.inhorse.out
3 3 1 1 1 1 3 32 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