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)라 하자. 한 가지 방법으로,

• 처음에 2번 버스를 타고 교차점 (5, 1)에서 내려,
• 4번 버스를 타고 (5, 5)에서 내리고,
• 5번 버스를 탄 후 (7, 5)에서 내려,
• 마지막으로 6번 버스를 타서 목적지 (7, 4)에서 내린다.

다른 방법으로,

• 7번 버스를 타고 (2, 5)에서 내려,
• 5번 버스를 타고 (7, 5)에서 내린 후,
• 마지막으로 6번 버스를 타서 목적지 (7, 4)에서 내린다.

입력

• 첫 번째 줄에 수직선의 수 m 과 수평선의 수 n 이 빈칸을 사이에 두고 주어진다(1 ≤ m,n ≤ 100,000).
• 두 번째 줄에 버스의 수 k (1 ≤ k ≤ 5,000)가 주어진다.
• 세 번째 줄부터 k 줄에 걸쳐 각 줄에 버스의 운행구간을 나타내는 5개의 수 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 이다.

출력

입출력 예

입력

7 6
8
1 2 1 2 2
2 1 1 5 1
6 7 3 7 6
7 2 1 2 6
3 3 2 6 2
4 5 6 5 1
5 1 5 7 5
8 3 5 6 5
2 1 7 4 

출력 

3

출처:2012 지역 본선 고등 3/5