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