Given N line segments. You should compute the intersection points between those segments using bentley-ottmann algorithm. 

Input

The first line of the input will contain the N.

Then each of the N following lines will contain the points of one of the line segments in the following format:

"x1 y1 x2 y2" where x1 and y1 are the coordinates of the start point of the line segment,

while x2 and y2 are the coordinates of the end point of the line segment. All the coordinates will be integers.

Output

The first line of the output should be the number of points computed lets say M.

Then each of the following M lines should contain one of the intersection points in the following format: "x y"

The points should be ordered by the x coordinate then the y coordinate.

The x and y should be rounded to 2 decimal places.

Example

Input:
2
1 2 4 2
2 0 2 4

Output:
1
2.00 2.00