Problem B. Highways - 2 ≡

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 (x_i, y_i) − (u_i, v_i). For each highway, either x_i = u_i or y_i = v_i. Starting town has coordinates (x_s, y_s), and destination town is at (x_d, y_d).

Input file format

Output file format

Constraints

Sample tests

0 1 14 5
2
0 0 0 10
0 5 15 5

18

50 40 90 100
3
7 8 10 8
7 8 7 30
7 8 7 3

-1