Description

You are given $N$ distinct points on the 2D plane, your task is to compute, for each point $(x_i, y_i)$, how many other points dominate this point. We say point $(x_a, y_a)$ dominates point $(x_b, y_b)$ if and only if $x_a \geq x_b$ and $y_a \geq y_b$

• Hint: Binary Indexed Tree (BIT) might be useful: you can refer to page 96 of this book for BIT implementation detail.

Input

The first line contains an integer $N$, the number of points.
Each of the next $N$ lines contains two integers, $x_i$ and $y_i$, the coordinates of the $i$-th point.

$N$
$x_1 \quad y_1$
$x_2 \quad y_2$
$\quad\vdots$
$x_N \quad y_N$

Constraints

• $1 \leq N \leq 2 \cdot 10^5$
• $1 \leq x_i, y_i \leq 10^9$
• All points $(x_i, y_i)$ are distinct

Subtasks

1. (Testcases 1~6): $N, x_i, y_i \leq 3 \cdot 10^3$
2. (Testcases 7~8): No additional constraint

Output

Output a single line with $N$ integers. The $i$-th integer should be the number of points that dominate the $i$-th point

Sample Input  Download

Sample Output  Download

Tags

Discuss