30291번 - Asteroid belt 서브태스크다국어

문제

Everyone thinks Prienai Way asteroid belt is filled with asteroids, but Lukas has a map with empty parts of the belt shown on it. In the map, asteroid belt is divided into M × N squares, each of which is either empty or full of asteroids.

Lukas wants to fly through the asteroid field. Naturally, he can only fly through empty squares.

Lukas’s spaceship can fly horizontally as long as needed, but it uses fuel to fly vertically – 1 fuel unit per each square passed vertically. Lukas’s destination is a planet in square (X₂, Y₂).

Figure out the smallest amount of fuel Lukas will need to consume to reach the destination.

입력

There are two numbers on the first line: asteroid field length M and height N. Lukas’s starting coordinates X₁ and Y₁, and the destination planet coordinates X₂ ir Y₂ are presented on the second line. The third line contains a single integer K – the number of empty regions.

Each of the following K lines consist of three natural numbers: h_i, a_i, b_i, meaning that in h_i-th row of the asteroid belt squares from a_i to b_i inclusively are free.

Both the starting point and the destination belongs to one of the K empty regions. No pair of empty regions that are on the same row touch or cross.

출력

Output one integer – lowest possible amount of fuel needed to reach the destination. If it is impossible to reach the destination, output -1.

제한

• 1 ≤ X₁, X₂ ≤ M
• 1 ≤ Y₁, Y₂ ≤ N, 1 ≤ ai ≤ bi ≤ M
• 1 ≤ h_i ≤ N.

서브태스크

힌트