Problems
Walrus on the blocks of ice
Walrus on the blocks of ice
Walrus Alexander is in the ocean at the point (\textbf{x_A},\textbf{y_A}). There are a lot of ice blocks around him. He wants to reach the point (\textbf{x_B},\textbf{y_B}), using the minimum number of jumps. Alexander can jump at most over two points in the one of four directions. If he is at the point (\textbf{x},\textbf{y}), then in one jump he can fall into one of the following cells: (\textbf{x+1},\textbf{y}), (\textbf{x-1},\textbf{y}), (\textbf{x},\textbf{y+1}), (\textbf{x},\textbf{y-1}), (\textbf{x+2},\textbf{y}), (\textbf{x-2},\textbf{y}), (\textbf{x},\textbf{y+2}), (\textbf{x},\textbf{y-2}). Alexander will jump to cell only if it’s located on an ice block. It’s guaranteed that the point (\textbf{x_A},\textbf{y_A}) and (\textbf{x_B},\textbf{y_B}) are on the ice blocks.
\InputFile
The first line gives four integers - the coordinates of points (\textbf{x_A},\textbf{y_A}) and (\textbf{x_B},\textbf{y_B}) (\textbf{1 }≤ \textbf{x_i,y_i} ≤ \textbf{10^9}). Coordinates of ice blocks will be given in segments. The second line is the number of segments \textbf{n} (\textbf{1 }≤ \textbf{n} ≤ \textbf{10^5}). Each of the following \textbf{n} lines contains three integers: \textbf{x} (\textbf{1 }≤ \textbf{x} ≤ \textbf{10^9}), \textbf{y_L} and \textbf{y_R} (\textbf{1 }≤ \textbf{y_L}≤\textbf{y_R} ≤ \textbf{10^9}). This means that points with coordinates (\textbf{x},\textbf{ y_i}) (\textbf{y_\{L \}}≤ \textbf{y_\{i \}}≤ \textbf{y_R}) are located on the ice blocks. The total number of such points doesn’t exceed \textbf{10^5}.
\OutputFile
The minimum number of jumps in which Alexander gets from point (\textbf{x_A},\textbf{y_A}) to the point (\textbf{x_B},\textbf{y_B}), or \textbf{-1} if it’s impossible.
Input example #1
1 1 3 4 3 1 1 1 2 1 4 3 4 4
Output example #1
4