Problem B. Highways - 2

Author:A. Klenin, T. Chistyakov   Time limit:2 sec
Input file:input.txt   Memory limit:20 Mb
Output file:output.txt  

Statement

There exist a number of small towns in the countryside, which were built after a careful planning. The towns are connected with the highways, which are perfectly straight and go either in north-south or east-west direction. Movement is allowed in both directions on every highway.

Sometimes towns are located at the middle of a highway, not necessarily at its ends. However, a highway always starts at a town and ends at a town.

When two highways cross each other, one of them goes above the other, so drivers don't have to slow down. Therefore it's not possible to get from one highway to another at such crossings. However, if two highways cross at a town, special exits are built, and it's possible to turn from one highway to another.

A highway never has common part with any other highway. In other words, the only locations when two highways may have a common point are towns. Two highways never have more than one common point.

Your task is to calculate the shortest distance that a traveller needs to drive to get from one given town to another.

There are M highways, given as a lines (xi, yi) − (ui, vi). For each highway, either xi = ui or yi = vi. Starting town has coordinates (xs, ys), and destination town is at (xd, yd).

Input file format

Input file contains integers xs ys xd yd M followed by M quartets of integers xi yi ui vi  — coordinates of the beginning and the ending town of each highway.

Output file format

Output file must contain a single number — the length of shortest path between given towns, or  − 1, if the path does not exist.

Constraints

1 ≤ M ≤ 1000, 0 ≤ xi, yi, ui, vi ≤ 106

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
0 1 14 5
2
0 0 0 10
0 5 15 5
18
2
50 40 90 100
3
7 8 10 8
7 8 7 30
7 8 7 3
-1

0.071s 0.010s 13