D. Nested Segments
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You 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·105) — the number of segments on a line.

Each of the next n lines contains two integers l i and r i ( - 109 ≤ l i < r i ≤ 109) — 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
41 82 34 75 6
Output
3010
Input
33 41 52 6
Output
011