Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.

Chef is working with the development of a new city Krewsko. He and other city planners are designing the transportation system of Krewsko. They are using Cartesian coordinates and Krewsko will only have roads that are parallel to either the x-axis or the y-axis.

It is clear that we need to add one set of traffic lights at every intersection of roads where a person has at least two other directions to continue their trip when arriving at the intersection. Your task is to count how many traffic light sets should be deployed. In particular, for each road you want to know how many traffic light sets will appear on that road.

Let's formalize how a road in the city is defined. A road is a segment on the plane with endpoints in X_{i,1}, Y_{i,1} and X_{i,2}, Y_{i,2} for i^{th} line. You are guaranteed that each line segment is either a vertical line or a horizontal line. An intersection is a point that belongs to two line segments: one horizontal and another vertical. We guarantee that no two vertical lines will share a point and no two horizontal lines share a point.

You must put a set of lights at each intersection of a horizontal and a vertical line segment where the point of intersection is not an endpoint of both segments.

------ Input ------

The first line of the input contains an integer N indicating number of roads.
The next N lines contain 4 integers each. The ^{i}th line contain X_{i,1}, Y_{i,1} and X_{i,2}, Y_{i,2}.

------ Output ------

The output consists of two lines. The first line contains a single
integer indicating the number of sets of lights that will be used
throughout all of Krewsko. The second line consists of N
integers. The i'th such integer indicates the number of traffic light
sets that will be deployed to the i'th road. There should be a single space between consecutive integers on this line.

------ Constraints ------

$1 ≤ N ≤ 10^{5}$
$1 ≤ X_{i,1} ≤ 10^{5}$
$1 ≤ Y_{i,1} ≤ 10^{5}$
$1 ≤ X_{i,2} ≤ 10^{5}$
$1 ≤ Y_{i,2} ≤ 10^{5}$
$The length of each road is positive and each road will either be a horizontal line segment or a vertical line segment.$

------ Subtasks ------

$Subtask #1 [40 points]: N ≤ 10000$
$Subtask #2 [60 points]: No additional constraints$

------ Example ------

Input:
4
2 1 2 6
1 3 5 3
4 1 4 4
1 5 5 5
Output:
3
2 2 1 1

见题面

见题面