Recently, Xiao Cong came to Stardew Valley to start farming and get rich to forget the hustle and bustle of the city. However, since Xiao Cong spent all his money on gacha, he did not have enough money to buy seeds. To collect enough money to raise pigs, Xiao Cong must start a large-scale wild vegetable foraging operation.

Stardew Valley is an infinitely large two-dimensional plane, and you can move freely within this plane. Xiao Cong may find wild vegetables on $n$ line segments in Stardew Valley, but these line segments are directed, and Xiao Cong must move along the direction of the line segment to find the wild vegetables. To find more wild vegetables, Xiao Cong hopes to traverse every place in Stardew Valley where wild vegetables might appear. In other words, for each line segment, Xiao Cong needs to traverse every point of that line segment along its direction. Of course, Xiao Cong can choose to traverse a line segment in multiple parts; specifically, Xiao Cong can leave the line segment at any position and re-enter it at any position, as long as the union of the paths covers the directed line segment.

Xiao Cong hopes to find a path that is as short as possible. This path should consist of $m$ line segments and cover the $n$ directed line segments in Stardew Valley. Xiao Cong can choose any point in Stardew Valley as the starting point of the path, and it must also be the endpoint of the path, meaning Xiao Cong must eventually return to the starting position.

Now, Xiao Cong has to go write his Connect Four assignment, and he doesn't know how to plan his walking route to minimize the distance he travels, so he has left this arduous task to you.

Note: If some parts of two line segments overlap and have the same direction, then when you walk through this part, we consider this part of both line segments to have been traversed.

Input

The first line contains an integer $n$, representing the number of directed line segments in the graph.

The next $n$ lines each contain four integers $x_1, y_1, x_2, y_2$, representing a directed line segment from $(x_1, y_1)$ to $(x_2, y_2)$.

Output

The first line should contain an integer $m$, representing the number of points in the polygonal path Xiao Cong takes, which must satisfy $m \le \min(5n^2, 5 \times 10^5)$.

The next $m$ lines should output the points on the path in order. Each line should contain two floating-point numbers $x, y$, used to describe the horizontal and vertical coordinates of a point. $x$ and $y$ should be kept to no more than 5 decimal places.

Examples

Input 1

3
0 0 0 100
0 100 100 100
100 100 0 0

Output 1

4
0 0
0 100
100 100
0 0

Note 1

Xiao Cong traveled a total distance of $200 + 100\sqrt{2}$, which is the optimal solution for this example.

Input 2

3
0 0 0 100
1 51 1 49
0 100 0 0

Output 2

5
0 0
0 100
1 51
1 49
0 100

Note 2

In this solution, Xiao Cong traveled a total distance of $202 + \sqrt{2402} + \sqrt{2602}$, but this is not the optimal solution for this data.

Subtasks

For each test case, if your output format does not meet the requirements, or if your output path does not cover the given $n$ directed line segments, the test case will receive 0 points. Otherwise, we will calculate the length $d$ of the path you provided and calculate your score based on 10 scoring parameters $a_1 \ge a_2 \ge \dots \ge a_{10}$:

$\max\{i \mid d \le a_i, 1 \le i \le 10\}$

The data guarantees that $a_1$ is large enough to ensure that a valid solution can receive at least 1 point.