Given a square chessboard of A x B size, the position of Knight (C, D) and position of a target (E, F) is given. Write a program to find out the minimum steps a Knight will take to reach the target position.

  • The above figure describes the movements for a knight (8 possibilities).
  • If the knight can not move from the source point to the destination point, then return -1.
  • A knight cannot go out of the board.

Example

Input: A = 6, B = 6, C = 1, D = 1, E = 4, F = 5
Output: 3
Explanation: The size of the chessboard is 6x6, the knight is initially at (1, 1) and the knight wants to reach position (4, 5).The minimum number of moves required for this is 3. (1,1)->(3,2)->(5,3)->(4,5)

Input Format

Following is the description of the parameters of the function "knight()":

int A and int B: denotes the size of the chessboard
int C and int D: denotes the position of the Knight
int E and int F: denotes the target of the Knight