16784번 - Golf 서브태스크다국어

JOI-kun is a boy practicing golf in a special golf course.

The course is a plane with xy-coordinates. There are N obstacles on the course. The i-th obstacle (1 ≤ i ≤ N) occupies the rectangular region whose x-coordinates are greater than or equal to A_i and less than or equal to B_i, and y-coordinates are greater than or equal to C_i and less than or equal to D_i. Two obstacles (including their boundaries) do not intersect with each other.

In this course, the start point is (S, T), and the end point is (U, V). These points are different, and not contained in any obstacles and their boundaries. In the beginning, the golf ball is placed at the start point.

JOI-kun can hit the golf ball, and move it for any distance toward any of four directions parallel to one of the coordinates of the plane. But, the track of the ball should not touch the interior of any obstacles. The ball can pass through the boundaries of the obstacles. It can stop on the boundary of an obstacle. Then, it can change the direction to move by hitting it toward the direction in which there is no obstacle.

JOI-kun wants to know the minimum number of hits needed to finish the course. Because you are JOI-kun’s golf friend, he asks you to calculate it.

What is the minimum number of hits needed to move the ball from the start point to the end point?

Given the information of the golf course, write a program which calculates the minimum number of hits needed to move the ball from the start point to the end point.

Read the following data from the standard input.

• The first line of input contains four space separated integers S, T, U, V. This means the x-coordinate of the start point is S , the y-coordinate of the start point is T, the x-coordinate of the end point is U, and the y-coordinate of the end point is V.
• The second line of input contains an integer N, the number of obstacles.
• The i-th line (1 ≤ i ≤ N) of the following N lines contains four space separated integers A_i, B_i, C_i, D_i. This means the i-th obstacle occupies the rectangular region whose x-coordinates are greater than or equal to A_i and less than or equal to B_i, and y-coordinates are greater than or equal to C_i and less than or equal to D_i.

Write one line to the standard output. The output contains the minimum number of hits needed to move the golf ball from the start point to the end point.

All input data satisfy the following conditions.

• 1 ≤ S ≤ 1 000 000 000.
• 1 ≤ T ≤ 1 000 000 000.
• 1 ≤ U ≤ 1 000 000 000.
• 1 ≤ V ≤ 1 000 000 000.
• 1 ≤ N ≤ 100 000.
• 1 ≤ A_i < B_i ≤ 1 000 000 000 (1 ≤ i ≤ N).
• 1 ≤ C_i < D_i ≤ 1 000 000 000 (1 ≤ i ≤ N).
• (S, T) ≠ (U, V).
• Two obstacles (including their boundaries) do not intersect with each other.
• The start point and the end point are not contained in any obstacles and their boundaries.

• S ≤ 1 000.
• T ≤ 1 000.
• U ≤ 1 000.
• V ≤ 1 000.
• N ≤ 1 000.
• B_i ≤ 1 000 (1 ≤ i ≤ N).
• D_i ≤ 1 000 (1 ≤ i ≤ N)

• N ≤ 1 000.

There are no additional constraints.