Bessie's Escape from the Knight-Guarded Forest

Bessie has inadvertently entered a castle in a forest guarded by knights. To return home, she must traverse the forest and complete the knights’ task: find a special shrub from a marked bush region and deliver it to the knights. The forest is modeled as a grid of W × H cells (with 1 ≤ W, H ≤ 1000) laid out in a Cartesian coordinate system (0-indexed). Some cells are impassable due to natural hazards or dangerous creatures.

Before picking up a shrub, Bessie is not allowed to enter the knight’s cell. Bessie has marked her starting location, the knight’s location and the entire region where the shrub grows on the map. To ensure she does not get lost, she can only move in the four cardinal directions (North, East, South, West), moving from one cell to an adjacent one in exactly one day.

Your task is to help Bessie determine the minimum number of days needed to complete her mission. She must first travel from her starting cell to any cell within the designated bush region (in order to pick up the shrub), and then proceed to the knight’s cell. Remember that while searching for the shrub, the knight’s cell is treated as an obstacle.

The problem can be solved using two phases of Breadth-First Search (BFS): one from Bessie’s starting location (with the knight’s cell blocked) to all cells in the bush region, and the other from the knight’s cell (with normal obstacle rules) to all cells in the bush region. The answer is the minimum sum of the distances for a cell belonging to the bush region that is reachable in both phases.

The formula for the answer is:

$$\min_{(x,y) \in \text{Bush Region}}\{d_{start}(x,y) + d_{knight}(x,y)\} $$

inputFormat

The input consists of several lines:

1. The first line contains two integers, W and H, representing the width and height of the grid.
2. The second line contains two integers, Bx and By, the x and y coordinates of Bessie's starting position.
3. The third line contains two integers, Kx and Ky, the x and y coordinates of the knight's position.
4. The fourth line contains four integers, x1, y1, x2, y2, defining the bush region. Here (x1, y1) is the bottom-left cell and (x2, y2) is the top-right cell of the rectangular region (inclusive) where the shrub grows.
5. The fifth line contains an integer N, the number of obstacle cells.
6. Each of the next N lines contains two integers xi and yi, the coordinates of an obstacle cell.

Notes:

• The grid cells are referenced by their (x, y) coordinates where 0 ≤ x < W and 0 ≤ y < H.
• Bessie cannot enter an obstacle cell. In the first phase (before obtaining the shrub), the knight's cell is also considered an obstacle.
• It is guaranteed that Bessie can complete the task.

outputFormat

Output a single integer representing the minimum number of days required for Bessie to first reach any cell in the bush region and then move to the knight’s cell.

sample

3 3
0 0
2 2
1 1 1 1
0

4

</p>