버스 갈아타기

2차원 평면에 m개의 수직선과 n개의 수평선으로 이루어진 격자 모양 도로망이 있다. 아래 그림은 7개의 수직선과 6개의 수평선으로 이루어진 도로망이다.

수직선과 수평선이 만나는 교차점 중 가장 왼쪽 아래 점은 (1, 1), 가장 오른쪽 위 점은 (m, n)이다.

이 도로망을 운행하는 버스가 k대 있다. 각 버스는 하나의 수평선 위에 있는 두 교차점 사이의 선분, 또는 하나의 수직선 위에 있는 두 교차점 사이의 선분을 왕복 운행한다. 각 버스는 자신이 운행하는 선분 위의 모든 교차점에서 정차하며, 선분의 양 끝 교차점에서도 정차한다.

출발지 교차점과 목적지 교차점이 주어진다. 두 교차점은 서로 다르다. 출발지에서 목적지까지 버스만 이용해 이동할 때, 타야 하는 버스의 최소 대수를 구하시오.

다음과 같이 8대의 버스가 운행한다고 하자.

• 1번 버스: (2, 1) - (2, 2)
• 2번 버스: (1, 1) - (5, 1)
• 3번 버스: (3, 2) - (6, 2)
• 4번 버스: (5, 6) - (5, 1)
• 5번 버스: (1, 5) - (7, 5)
• 6번 버스: (7, 3) - (7, 6)
• 7번 버스: (2, 1) - (2, 6)
• 8번 버스: (3, 5) - (6, 5)

출발지가 (2, 1), 목적지가 (7, 4)라면 7번 버스를 타고 (2, 5)에서 내려 5번 버스로 갈아탄 뒤, (7, 5)에서 내려 6번 버스로 갈아타면 목적지에 도착한다. 이때 이용하는 버스는 3대이며, 이것이 최소이다.

첫째 줄에 수직선의 수 m과 수평선의 수 n이 공백으로 구분되어 주어진다. (1 ≤ m, n ≤ 100,000)

둘째 줄에 버스의 수 k가 주어진다. (1 ≤ k ≤ 5,000)

다음 k개의 줄에는 각 버스의 운행 구간을 나타내는 다섯 정수 b, x1, y1, x2, y2가 공백으로 구분되어 주어진다. b는 버스 번호이며 1 ≤ b ≤ k이다. (x1, y1)과 (x2, y2)는 해당 버스가 운행하는 선분의 양 끝 교차점이다.

마지막 줄에는 출발지와 목적지 좌표를 나타내는 네 정수 sx, sy, dx, dy가 공백으로 구분되어 주어진다. (sx, sy)는 출발지, (dx, dy)는 목적지이다.

모든 좌표는 1 ≤ x1, x2, sx, dx ≤ m, 1 ≤ y1, y2, sy, dy ≤ n을 만족한다. 출발지와 목적지는 서로 다르며, 출발지에서 목적지로 이동하는 방법이 항상 하나 이상 존재한다.

첫째 줄에 출발지에서 목적지까지 이동하기 위해 이용해야 하는 버스의 최소 대수를 출력한다.