Bus Transfers

On a two-dimensional plane, a grid-shaped road network is formed by m vertical lines and n horizontal lines. The figure below shows a road network with 7 vertical lines and 6 horizontal lines.

Among all intersections of vertical and horizontal lines, the bottom-left intersection is (1, 1), and the top-right intersection is (m, n).

There are k buses running on this road network. Each bus travels back and forth along either a segment between two intersections on one horizontal line, or a segment between two intersections on one vertical line. A bus stops at every intersection on its segment, including both endpoints.

You are given a start intersection and a destination intersection. They are different. Using only buses, find the minimum number of buses that must be taken to travel from the start to the destination.

Suppose 8 buses run as follows.

• Bus 1: (2, 1) - (2, 2)
• Bus 2: (1, 1) - (5, 1)
• Bus 3: (3, 2) - (6, 2)
• Bus 4: (5, 6) - (5, 1)
• Bus 5: (1, 5) - (7, 5)
• Bus 6: (7, 3) - (7, 6)
• Bus 7: (2, 1) - (2, 6)
• Bus 8: (3, 5) - (6, 5)

If the start is (2, 1) and the destination is (7, 4), you can take Bus 7, get off at (2, 5), transfer to Bus 5, get off at (7, 5), and transfer to Bus 6 to reach the destination. This uses 3 buses, which is the minimum.

The first line contains the number of vertical lines m and the number of horizontal lines n, separated by a space. (1 ≤ m, n ≤ 100,000)

The second line contains the number of buses k. (1 ≤ k ≤ 5,000)

Each of the next k lines contains five integers b, x1, y1, x2, y2, separated by spaces. They describe one bus route. b is the bus number, with 1 ≤ b ≤ k. The points (x1, y1) and (x2, y2) are the two endpoint intersections of that bus route segment.

The last line contains four integers sx, sy, dx, dy, separated by spaces. (sx, sy) is the start, and (dx, dy) is the destination.

All coordinates satisfy 1 ≤ x1, x2, sx, dx ≤ m and 1 ≤ y1, y2, sy, dy ≤ n. The start and destination are different, and at least one route from the start to the destination always exists.

Print one integer: the minimum number of buses needed to travel from the start to the destination.