Color Balls

Interview

Time limit1sMemory limit256 MB

Summary

For each ball, add up the sizes of all strictly smaller balls with a different color.

Level: Medium5 of 10
Topics: Sorting, Prefix sum, Hash map
Solved: No attempts yet

Problem

Jihoon plays a computer game with several players in it. Each player controls one ball that has a fixed color and a fixed size. A player scores by capturing a ball that is strictly smaller than their own ball and has a different color, and the score gained is the size of the captured ball. A ball of the same size cannot be captured even when its color differs. Capturing another ball does not change the color or the size of your own ball.

Consider four balls. Colors are written as numbers for convenience.

Ball	Color	Size
1	1	10
2	3	15
3	1	3
4	4	8

Ball 2 captures all three other balls. Ball 1 cannot capture ball 2, which is larger, and cannot capture ball 3, which has the same color, so it captures only ball 4.

Given the color and the size of every ball, print for each player the total size of all balls that player can capture.

Input

The first line contains the number of balls $N$ ( $1 \le N \le 200\,000$ ).

Each of the next $N$ lines contains the color $C_i$ and the size $S_i$ of the $i$ -th ball, separated by a space ( $1 \le C_i \le N$ , $1 \le S_i \le 2\,000$ ). Several balls may share a color, and several balls may share a size.

Output

Print $N$ lines. The $i$ -th line contains the total size of all balls that the player controlling the $i$ -th ball can capture.

Examples8

Example 1
Input
```
4
1 10
3 15
1 3
4 8
```
Expected output
```
8
21
0
3
```
Example 2
Input
```
3
2 3
2 5
2 4
```
Expected output
```
0
0
0
```
Example 3
Input
```
1
1 1
```
Expected output
```
0
```
Example 4
Input
```
2
1 5
2 5
```
Expected output
```
0
0
```
Example 5
Input
```
2
1 4
2 7
```
Expected output
```
0
4
```
Example 6
Input
```
5
1 1
2 2
3 3
4 4
5 5
```
Expected output
```
0
1
3
6
10
```
Example 7
Input
```
6
1 5
2 5
1 3
2 3
3 1
3 1
```
Expected output
```
5
5
2
2
0
0
```

Example 8

Input

Expected output