Ice Block Puzzle

Deep in the Antarctic legend there lies a vast icy plain divided into equal square cells. Hidden beneath this frozen wasteland are the ruins of a prehistoric civilization. Scattered on the ice plain are several rectangular icebergs, each spanning one or more full cells. These icebergs do not overlap and are never adjacent (not even at a corner).

Legend holds that in a deep hole (of one cell) in the ice, a mysterious switch was placed by ancient people. To activate the switch, one must slide a small movable ice block – a piece that is nearly one full cell in size. Since natural ice blocks of that size cannot exist on the plain, it is clear that this movable ice block is also a product of the prehistoric civilization. The ACM exploration team intends to push this ice block into the deep hole in order to open a passage to the lower levels of the ice plain and uncover long‐lost secrets.

The ice surface is perfectly smooth. A gentle push causes the ice block to slide in one of the four grid directions. Once pushed, the block continues to slide until it is about to enter a cell which is either outside the boundary of the ice field or occupied by an iceberg – in which case it stops in the last free cell. Note that the ice block can glide through any ice‐covered region as long as it is not blocked by an iceberg, and it may even pass between icebergs if there is a gap. The starting position of the ice block and the deep hole are guaranteed not to be adjacent to any iceberg.

Your task is to compute the minimum number of pushes required to slide the ice block into the deep hole.

Movement simulation:

When the ice block is pushed in a direction (up, down, left, right), let its current cell be (x,y). It will move cell by cell in that direction. At each step, if the next cell is within the grid and is not occupied by an iceberg, the block continues. Otherwise, it stops at the last valid (free) cell. The grid is 1-indexed.

Input/Output example: If the ice field is 5×5, the ice block starts at (2,2) and the deep hole is at (5,2) with no icebergs present, a single push downward will slide the block into the hole (since the boundary stops it exactly on (5,2)).

inputFormat

The first line contains two integers R and C (1 ≤ R, C ≤ 1000) which denote the number of rows and columns of the grid.

The second line contains two integers s_r and s_c (1-indexed) – the starting row and column of the ice block.

The third line contains two integers d_r and d_c (1-indexed) – the row and column of the deep hole.

The fourth line contains an integer N – the number of rectangular icebergs on the ice plain.

Each of the following N lines contains 4 integers: r₁, c₁, r₂, c₂ (1-indexed, with r₁ ≤ r₂ and c₁ ≤ c₂) describing an iceberg that covers all cells in the rectangle from (r₁, c₁) to (r₂, c₂).

It is guaranteed that the ice block's starting cell and the deep hole cell are NOT adjacent (including diagonals) to any iceberg.

outputFormat

Output a single integer – the minimum number of pushes required to push the ice block into the deep hole. If it is impossible, output -1.

sample

5 5
2 2
5 2
0

1