TCSome of the more elite (and not-so-elite) coders around take part in a contest called TC. In TC, there are multiple types of competitions. Here, we consider the Algorithm and TCHS competition types. For each type, each competitor receives a rating, an integer between 1 and 100000, inclusive. A coder's rating is based upon his or her level of performance in single round matches (SRMs) and is calculated using a complicated formula.
Each SRM has three problems, usually called the 250, 500, and 1000 because of their most frequently occurring point values, although they can sometimes have slightly different values, such as 300, 550, and 900. In Algorithm SRMs, the 250 is usually fairly easy, the 500 requires some thought, and can be quite difficult, and the 1000 is usually very difficult, accessible only to those with an advanced knowledge of algorithms and well-honed problem-solving skills. In TCHS SRMs, in which only high school students are allowed to participate, the 250 and 500 are usually fairly easy, and the 1000 is most often not harder than an average problem from a typical national olympiad contest.
The interesting thing is that there's a speed factor too - a coder gets no points for a solution if it is even slightly wrong (i.e. does not pass all of the test cases). Instead, partial scoring is based upon the time taken for a coder to submit his or her final solution for that problem. A coder who solves the 250 and 500 quickly may earn more points than a coder who solves only the 1000, but takes a long time to do so.
Although the TCHS and Algorithm ratings for a coder who has participated in both TCHS and Algorithm SRMs lately are usually close, this is not always the case. In particular, TCHS is more about speed, since many coders are able to solve all three problems, whereas Algorithm SRMs require more thinking and there is a steeper curve in terms of problem difficulty.
You are given N coders (1 ≤ N ≤ 300000), conveniently numbered from 1 to N. Each of these coders participates in both TCHS and Algorithm contests. For each coder, you are also given an Algorithm rating Ai and a TCHS rating Hi. Coder i is said to be better than coder j if and only if both of coder i's ratings are greater than or equal to coder j's corresponding ratings, with at least one being greater. For each coder i, determine how many coders coder i is better than.
On the first line of input is a single integer N, as described above.
N lines then follow. Line i+1 contains two space-separated integers, Ai and Hi.
Line i should contain the number of coders that coder i is better than.
9 2156 1789 862 700 1106 1041 1568 1557 2575 1984 1033 950 1738 1649 1097 1089 1774 1630
7 0 2 4 8 1 5 2 5
Point Value: 15 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Jan 27, 2009
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Note that for a given pair of coders, it is possible that neither is better than the other. There is nothing unusual about this.