A courier drone moves across a rectangular board of R rows and C columns like a chess knight: from a cell it may jump to any cell that is two rows and one column away, or one row and two columns away, provided the landing cell is on the board. Cells are addressed by 0-indexed (row, column).
Given a start cell and a target cell, report the fewest jumps needed to move the courier from the start to the target. If the target cannot be reached, report -1. If the start and target are the same cell, the answer is 0.
Input format
Line 1: two integers R and C.
Line 2: four integers r1 c1 r2 c2, the start cell (r1,c1) and the target cell (r2,c2).
Output format
A single integer: the fewest knight jumps, or -1 if the target is unreachable.
Constraints
- 1 <= R, C <= 300
- 0 <= r1, r2 < R and 0 <= c1, c2 < C