Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. Nested Segments

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given *n* segments on a line. There are no ends of some segments that coincide. For each segment find the number of segments it contains.

Input

The first line contains a single integer *n* (1 ≤ *n* ≤ 2·10^{5}) — the number of segments on a line.

Each of the next *n* lines contains two integers *l*_{i} and *r*_{i} ( - 10^{9} ≤ *l*_{i} < *r*_{i} ≤ 10^{9}) — the coordinates of the left and the right ends of the *i*-th segment. It is guaranteed that there are no ends of some segments that coincide.

Output

Print *n* lines. The *j*-th of them should contain the only integer *a*_{j} — the number of segments contained in the *j*-th segment.

Examples

Input

4

1 8

2 3

4 7

5 6

Output

3

0

1

0

Input

3

3 4

1 5

2 6

Output

0

1

1

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/26/2017 01:17:42 (c3).

Desktop version, switch to mobile version.
User lists

Name |
---|