Dark streets

Many streets in the evening city are dark after a massive power outage and the traffic situation is rather chaotic. The group of Malagasy paleontologists is heading from the museum where they had a ceremonial dinner to the hotel where they are accommodated. Lantoniaina Bezanozano, the bus driver of the group, insists that for the safety reasons in the foreign city they should drive preferably through the illuminated streets and avoid the dark streets even if this makes their journey longer. He wants to minimize the number of dark streets on the route from the museum to the hotel.



Image 1. Plan of the illuminated and the dark streets in the city. The crossings at the museum and at the hotel are marked. The green line represents one of more possible routes from the museum to the hotel. There are 4 dark streets on this route and it is the minimum possible number of dark streets on any route from the museum to the hotel.

The task

You are given the plan of the city and the list of all illuminated streets. Find the route between two given street crossings which goes through the minimum number of dark unilluminated streets. We consider each connection between two neighbouring crossings to be a separate street.


Input

The first line contains tree positive integers N, M, L separated by spaces. The city is represented by a rectangular street grid with s M × N nodes. The grid has N nodes (crossings) in the horizontal (east-west) direction and M nodes in the vertical (north-south) direction. Each node represents one street crossing. Each edge connecting two neighbouring nodes horizontally or vertically represents a separate street. Each crossing has two coordinates. The first coordinate is the minimum number of the streets on the route between the crossing and the western border of the city, the second coordinate is the minimum number of the streets on the route between the crossing and the southern border of the city.
The second line contains four integers separated by spaces. The first two integers represent the coordinates of the crossing closest to the museum, the second two integers represent the coordinates of the crossing closest to the hotel.
Next, there are L lines. Each line specifies one illuminated area of the city. The illuminated area is a rectangle which sides coincide with the city streets and which corners coincide with some street crossings. The rectangle is considered as an area, it contains its border and also its whole interior. A line specifying an illuminated area contains four positive integers separated by spaces. The first integers two represent the coordinates of the crossing in the south-western corner of the illuminated area and the second two integers represent the coordinates of the crossing in the north-eastern corner of the illuminated area. The illuminated areas defined in this way may overlap. On the other hand, no crossing is a part of more than 4 illuminated areas.
A particular street is illuminated if and only if there is an illuminated area which contains both crossings connected by this street. All streets are two-way streets.
The value M × N does not exceed 107, the value L does not exceed 105. The illuminated areas are listed in an arbitrary order.

Output

The output contains one text line with one integer equal to the minimum possible number of unilluminated streets on a route from the museum to the hotel.

Example 1

Input
9 5 15
3 1 8 0
0 2 0 4
1 0 1 2
1 3 1 4
2 2 2 3
1 1 2 1
0 2 2 2
0 3 3 3
3 3 4 4
4 2 5 4
4 0 5 0
5 0 5 1
5 1 6 1
6 2 7 3
7 3 8 3
7 1 7 2

Output
4
The data and the output of the example 1 are illustrated in the image 1.

Example 2

Input
20 20 4
5 5 15 15
0 0 19 0
0 0 0 19
0 19 19 19
19 0 19 19
Output
9

Example 3

Input
20 20 2
1 1 18 18
13 14 19 19
0 0 7 9
Output
11

Example 4

Input
3162 3162 3
100 2500 3000 100
0 1900 2000 2000
1900 0 2000 2000
100 100 1000 1000
Output
1500

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set