Last night I saw you running In the open fields of grace No longer were you broken or in pain

You have found an endless field, where you have forgotten your broken and painful past. You run like a child in the grace of God.

However, you have discovered a problem: there are several canyons in this field. You are in danger of falling into a canyon at any time. To continue running freely, you decide to enclose these canyons with several fences.

We can ignore the width of the canyons and treat each canyon as a line segment. These line segments may intersect, and your fence must be one or more closed curves that do not self-intersect and do not intersect each other, such that every canyon is completely contained within the closed region enclosed by one of the closed curves.

Of course, the fence requires resources, and the resources consumed are proportional to the length of the fence. You wish to minimize the total amount of resources consumed, so you want to find the infimum of the total length of the fence. In other words, you want to find the largest real number $x$ such that there is no scheme where the total length of the fence is less than $x$.

Input

The first line of the input contains an integer $n$, representing the number of canyons.

The next $n$ lines each contain four integers $a_i, b_i, c_i, d_i$, representing the $i$-th canyon as a line segment connecting point $(a_i, b_i)$ and point $(c_i, d_i)$. It is guaranteed that the two endpoints do not coincide, different line segments do not involve the same points, and no three points are collinear.

Output

Output a single real number representing the infimum of the total length of the fence. The absolute or relative error between your answer and the standard answer must not exceed $10^{-6}$.

Examples

Input 1

1
0 0 0 1

Output 1

2.00000000

Note 1

A rectangle with four endpoints at $(-0.01, -0.01), (-0.01, 1.01), (0.01, 1.01), (0.01, -0.01)$ completely contains the input line segment, and its total length is $2.08$, which is slightly greater than the infimum.

We can prove that there is no scheme with a length of exactly $2$. We can construct a scheme with a length arbitrarily close to $2$ by "tightening" the rectangle infinitely toward the input line segment.

Input 2

4
-1 7 0 7
0 0 0 1
2 -3 5 5
2 2 6 -1

Output 2

23.563573998194637061425470524757

Note 2

The figure below shows the input line segments; note that the line segments can intersect:

Figure 1: Explanation of Example 2

We can construct a scheme with any total length greater than the answer by infinitely "approaching" these red curves. Note that from Example 1, it is easy to see that the red line segment in the top-left corner is counted twice.

Input 3

4
-1 1 -1 3
0 4 2 4
3 1 3 3
0 0 2 0

Output 3

13.656854249492380195206754896839

Note 3

The answer is $8 + 4\sqrt{2}$. The explanation is shown in the figure:

Figure 2: Explanation of Example 3

We can construct a scheme with any total length greater than $8 + 4\sqrt{2}$ by infinitely "approaching" these red curves.

Input 4

See fields/fields4.in and fields/fields4.ans in the contestant directory.

Constraints

• For 5% of the data, $1 \le n \le 1$.
• For 10% of the data, $1 \le n \le 2$.
• For 15% of the data, $1 \le n \le 10$.
• For 30% of the data, $1 \le n \le 15$.
• For 45% of the data, $1 \le n \le 30$.
• For 55% of the data, $1 \le n \le 60$.
• For 65% of the data, $1 \le n \le 120$.
• For 75% of the data, $1 \le n \le 200$.
• For an additional 10% of the data, the answer contains at most two curves.
• For 100% of the data, $1 \le n \le 250$, $0 \le |a_i|, |b_i|, |c_i|, |d_i| \le 10^9$. It is guaranteed that the two endpoints do not coincide, different line segments do not involve the same points, and no three points are collinear.