Minimum Moves to Target

You are given an infinite grid where each cell is identified by its row and column indices. You start at cell \( (s_i, s_j) \) and your goal is to reach the target cell \( (t_i, t_j) \). However, some cells are blocked and cannot be traversed.

In one move, you can move from cell \( (x,y) \) to any of the four neighboring cells: up, down, left, or right. Formally, the allowed moves are to \( (x-1,y) \), \( (x+1,y) \), \( (x,y-1) \) and \( (x,y+1) \), provided that the destination cell is not blocked and is within a defined search boundary.

Your task is to find the minimum number of moves required to reach the target cell from the starting cell. If it is not possible to reach the target cell, output \( -1 \).

Note: Since the grid is infinite, when obstacles exist it is safe to restrict the search to a bounded region that covers the start, target, and all obstacles with a generous margin.

inputFormat

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

• The first line contains four space-separated integers: \( s_i, s_j, t_i, t_j \), representing the starting cell and the target cell.
• The second line contains a single integer \( n \), the number of blocked cells.
• The next \( n \) lines each contain two space-separated integers representing the coordinates of a blocked cell.

If \( n = 0 \), there are no blocked cells.

outputFormat

Output a single integer to standard output (stdout) - the minimum number of moves required to reach the target cell from the starting cell. If it is impossible, output \( -1 \).

0 0 3 3
3
1 0
1 1
1 2

6