Give you N (1 <= N <= 200000) intervals, represented as [A, B], for example, interval s represented as [As, Bs].

For two intervals s and t, we say S covered by T if At <= As and Bs <= Bt. Now my problem is easy, just tell me the question below: For each interval, how many intervals can cover it but not covered by it?

Input

The input contains multiple test cases.

For each test case, the first line is an integer N (1 <= N <= 200000), which is the number of intervals. Then come N lines, the i-th of which contains two integers: A_i and B_i (A_i, B_i will not exceed the 32-bit integer) specifying the two parameters described above.

Output

For each test case, output one line containing n space-separated integers, the i-th of which specifying the number of intervals that can cover it but not covered by it.

Example

Input:
3
0 1
-1 2
-2 3
2
0 1
0 1

Output:
2 1 0
0 0