Given a maze of size , whose lower-left corner is while upper-right corner is . And there are segment walls in the maze. One cannot cross the walls but can touch them or walk along them. Now a MI robot is assigned to go from to , as an intelligent robot, MI robot will automatically determine the shortest valid path and go along it. Print the length of the shortest valid path between and .

输入描述:

The first line contains three integers , denoting the size of the maze and the number of walls respectively.

Following k lines each contains four integers , denoting a segment wall .

The next line contains four integers , denoting the two given points.

It's guaranteed that no two segment walls share common points, and that no segment wall covers  or , and that either  or .

输出描述:

Only one line containing a real number with four decimal places after the decimal point, denoting the answer.

It's guaranteed that the fifth decimal place after the decimal point is neither 4 nor 5.

6 3 2
1 1 3 1
2 2 5 2
3 0 3 3

3.8284

One possible way is , and the exact answer is .