Walrus on the blocks of ice
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 at most over two points in the one of four directions. If he is at the point (x,y), then in one jump he can fall into 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 cell only if it’s located on an ice block. It’s guaranteed that the point (x_A,y_A) and (x_B,y_B) are on the ice blocks.
Input
The first line gives four integers - the coordinates of points (x_A,y_A) and (x_B,y_B) (1 ≤ x_i,y_i ≤ 10^9). Coordinates of ice blocks will be given in segments. The second line is the number of segments n (1 ≤ n ≤ 10^5). Each of the following n lines contains three integers: x (1 ≤ x ≤ 10^9), y_L and y_R (1 ≤ y_L≤y_R ≤ 10^9). This means that points with coordinates (x, y_i) (y_{L }≤ y_{i }≤ y_R) are located on the ice blocks. The total number of such points doesn’t exceed 10^5.
Output
The minimum number of jumps in which Alexander gets from point (x_A,y_A) to the point (x_B,y_B), or -1 if it’s impossible.