INTERVA2 - Interval Challenge


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: Ai and Bi ( Ai , Bi 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


hide comments
Felipe Getúlio: 2018-08-19 16:51:59

what is the obvious optimization?

pran4798: 2017-04-07 21:47:03

how we can use bitmask, please give me some hint.

VV: 2013-05-21 16:49:04

No kind of weird optimization required for this problem! Got AC in first try. Just do the obvious optimization.

Last edit: 2013-05-21 17:29:07
Pushkar Mishra: 2013-05-06 03:02:26

No IO optimizations required. Just avoid maps, and other predefined containers or classes.

Robin Lee: 2011-08-30 00:37:44

Writing solution: Fun.
Optimizing solution: Not fun.

Last edit: 2011-08-30 23:02:21
Ashish Massand: 2011-06-21 07:18:19

Got it forgot the fact that the interval shouldn't cover the interval that covers it.

Ashish Massand: 2011-06-21 07:17:40

Could someone explain the second test case. Shouldn't the answer be
1 1

:D: 2011-01-11 11:23:04

You probably can get away with standard I/O but it is highly dependent on implementation details. I would suggest doing both fast 'I' and 'O' :)

~!(*(@*!@^&: 2010-04-15 21:35:07

i dont use fast IO but I need to use C++ 4.3.2

P != NP: 2010-03-31 21:49:06

This is too much......It needs IO optimizations to get accepted.....I tried almost 15 times before i got AC.


Added by:Hemant Verma
Date:2009-11-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 NODEJS OBJC PERL6 SQLITE VB.NET
Resource:Alkhwarizm 2009