Teleport 3

Time limit2sMemory limit512 MB

Summary

Find the shortest travel time on a grid where you can walk one unit per second or take any of three two-way teleports costing 10 seconds each.

Level: Medium4 of 10
Topics: Graph, Shortest path, Implementation
Solved: No attempts yet

Problem

Subin lives on an infinite grid. Each point of the grid is a pair of integers $(x, y)$ .

Subin starts at $(x_s, y_s)$ and wants to reach home at $(x_e, y_e)$ .

There are two ways to move. The first is a jump. From $(x, y)$ Subin moves to one of $(x+1, y)$ , $(x-1, y)$ , $(x, y+1)$ , $(x, y-1)$ , and one jump takes 1 second.

The second is a teleport. Three teleports are fixed in advance, and each one is given by the four coordinates $(x_1, y_1)$ , $(x_2, y_2)$ . It carries Subin from $(x_1, y_1)$ to $(x_2, y_2)$ or from $(x_2, y_2)$ to $(x_1, y_1)$ , and one teleport takes 10 seconds. The same teleport may be used any number of times.

Given Subin's position and the position of the house, write a program that computes the shortest time to get home.

Input

The first line contains $x_s$ and $y_s$ , and the second line contains $x_e$ and $y_e$ . ( $0 \le x_s, y_s, x_e, y_e \le 10^9$ )

Each of the next three lines contains the information of one teleport, $x_1$ , $y_1$ , $x_2$ , $y_2$ . ( $0 \le x_1, y_1, x_2, y_2 \le 10^9$ )

All eight coordinates given in the input are distinct.

Output

Print the shortest time in seconds for Subin to get home.

Examples5

Example 1

Input

3 3
4 5
1000 1001 1000 1002
1000 1003 1000 1004
1000 1005 1000 1006

Expected output

Example 2

Input

0 0
20 20
1 1 18 20
1000 1003 1000 1004
1000 1005 1000 1006

Expected output

Example 3

Input

0 0
20 20
1000 1003 1000 1004
18 20 1 1
1000 1005 1000 1006

Expected output

Example 4

Input

10 10
10000 20000
1000 1003 1000 1004
3 3 10004 20002
1000 1005 1000 1006

Expected output

Example 5

Input

3 7
10000 30000
3 10 5200 4900
12212 8699 9999 30011
12200 8701 5203 4845

Expected output