Robot Arm Direction Changes

You are given a square grid of size (m \times m) (with indices from 0 to (m-1)) representing a workspace with obstacles. There are (n) robot arms, each having a starting position and a target position. The robot arms can move in four directions: right, down, left, and up. Every time a robot changes its moving direction (i.e. the chosen direction is different from its immediately previous direction), it counts as a direction change. The task is to determine the minimum number of direction changes required for each robot arm to reach its destination without colliding with any obstacles. If a robot cannot reach its destination, output -1 for that robot.

Input Specification:
The first line contains three space‐separated integers (n), (m), and (k) representing the number of robot arms, the grid size, and the number of obstacles respectively. The next (n) lines each contain four integers: (s_x), (s_y), (e_x), (e_y) representing the starting and ending coordinates of a robot. Then the next (k) lines each contain two integers (o_x) and (o_y) representing the coordinates of an obstacle. It is guaranteed that (0 \le s_x, s_y, e_x, e_y, o_x, o_y < m).

Output Specification:
For each robot arm, output a single integer on a new line indicating the minimum number of direction changes required, or -1 if the target cannot be reached.

inputFormat

The input is read from standard input (stdin) and has the following format:

n m k
s_x s_y e_x e_y
s_x s_y e_x e_y
... (n lines in total for robots)
 o_x o_y
 o_x o_y
... (k lines in total for obstacles)

For example:

2 5 1
0 0 4 4
1 1 3 3
2 2

outputFormat

For each robot, output a single line to standard output (stdout) containing the minimum number of direction changes required to reach its destination, or -1 if it is impossible.## sample

2 5 1
0 0 4 4
1 1 3 3
2 2

2
2