Some 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 ~100\,000~, 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.

Problem Statement

You are given ~N~ coders ~(1 \le N \le 300\,000)~, 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 ~A_i~ and a TCHS rating ~H_i~. 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.

Input Specification

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, ~A_i~ and ~H_i~.

Output Specification

Line ~i~ should contain the number of coders that coder ~i~ is better than.

Sample Input

9
2156 1789
862 700
1106 1041
1568 1557
2575 1984
1033 950
1738 1649
1097 1089
1774 1630

Sample Output

7
0
2
4
8
1
5
2
5