Bessie’s Ice Skating

Bessie is ice skating on a large frozen lake modeled as a 2-dimensional grid with coordinates in the range \( -10^9 \) to \( 10^9 \). There are \( N \) rocks on the lake and the remaining cells are slippery ice. Because Bessie isn’t a very good skater, she can only get moving by pushing herself away from a rock that is immediately adjacent to her current cell. When she does so, she slides in a straight line (north, east, south, or west) until she encounters another rock. Of course, she stops in the cell immediately before the rock.

Formally, if Bessie is at position \( (x,y) \) and there is a rock at cell \( (x-d_x,y-d_y) \) for some direction \( (d_x,d_y) \) (which guarantees that she is adjacent to a rock), then she can push herself in the direction \( (d_x,d_y) \). When sliding in that direction, she will continue until she finds the nearest rock along that line. For example, when pushing eastward (i.e. \( (1,0) \)), she will look for the rock in row \( y \) with the smallest \( x \)-coordinate greater than \( x \); if that rock is at \( (r_x,y) \), she will stop at \( (r_x-1,y) \). If no rock exists in that direction, the push is not allowed because she would never stop.

Bessie starts at \( (B_x,B_y) \), which is guaranteed to be adjacent to at least one rock, and her goal is to reach \( (G_x,G_y) \). Determine the minimum number of pushes required for Bessie to reach her goal.

Constraints:

• \( 1 \leq N \leq 20000 \)
• \( -10^9 \leq X_i, Y_i, B_x, B_y, G_x, G_y \leq 10^9 \)

inputFormat

The first line contains five integers: \( N \), \( B_x \), \( B_y \), \( G_x \), and \( G_y \). Each of the next \( N \) lines contains two integers \( X_i \) and \( Y_i \), indicating the position of the \( i \)-th rock. No two rocks are at the same position. It is guaranteed that Bessie’s starting cell is adjacent to at least one rock and that the goal is reachable.

outputFormat

Output a single integer representing the minimum number of pushes required for Bessie to reach her goal.

sample

2 0 0 1 0
-1 0
2 0

1