Urban Development

All submissions for this problem are available.
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 xaxis or the yaxis.
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
Author:  cenadar 
Tester:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/URBANDEV 
Tags  cenadar, linesweep, medium, nov16, segmenttree 
Date Added:  20112015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions