컬러볼

면접 대비

시간 제한1초메모리 제한256 MB

요약

각 공마다 자신보다 작고 색이 다른 모든 공의 크기 합을 구합니다.

난이도: 보통10점 중 5점
유형: 정렬, 누적 합, 해시맵
정답자: 아직 제출이 없습니다

문제

지훈이가 즐기는 컴퓨터 게임에는 여러 플레이어가 참여한다. 각 플레이어는 색과 크기가 정해진 공 하나를 조종한다. 플레이어의 목표는 자기 공보다 크기가 작고 색이 다른 공을 사로잡아 그 공의 크기만큼 점수를 얻는 것이다. 크기가 같은 공은 색이 달라도 사로잡지 못한다. 다른 공을 사로잡은 뒤에도 자기 공의 색과 크기는 변하지 않는다.

공이 네 개인 경우를 보자. 색은 편의상 숫자로 나타낸다.

공 번호	색	크기
1	1	10
2	3	15
3	1	3
4	4	8

2번 공은 나머지 세 공을 모두 사로잡는다. 1번 공은 자기보다 큰 2번 공과 색이 같은 3번 공을 사로잡지 못하므로 4번 공만 사로잡는다.

공의 색과 크기가 주어질 때, 각 플레이어가 사로잡을 수 있는 모든 공의 크기 합을 출력하는 프로그램을 작성하시오.

입력

첫 줄에 공의 개수 $N$ 이 주어진다 ( $1 \le N \le 200\,000$ ).

이어지는 $N$ 개의 줄 중 $i$ 번째 줄에는 $i$ 번째 공의 색 $C_i$ 와 크기 $S_i$ 가 공백으로 구분되어 주어진다 ( $1 \le C_i \le N$ , $1 \le S_i \le 2\,000$ ). 색이 같은 공이나 크기가 같은 공이 여럿 있을 수 있다.

출력

$N$ 개의 줄을 출력한다. $i$ 번째 줄에는 $i$ 번째 공을 조종하는 플레이어가 사로잡을 수 있는 모든 공의 크기 합을 출력한다.

예제8

예제 1
입력
```
4
1 10
3 15
1 3
4 8
```
예상 출력
```
8
21
0
3
```
예제 2
입력
```
3
2 3
2 5
2 4
```
예상 출력
```
0
0
0
```
예제 3
입력
```
1
1 1
```
예상 출력
```
0
```
예제 4
입력
```
2
1 5
2 5
```
예상 출력
```
0
0
```
예제 5
입력
```
2
1 4
2 7
```
예상 출력
```
0
4
```
예제 6
입력
```
5
1 1
2 2
3 3
4 4
5 5
```
예상 출력
```
0
1
3
6
10
```
예제 7
입력
```
6
1 5
2 5
1 3
2 3
3 1
3 1
```
예상 출력
```
5
5
2
2
0
0
```

예제 8

입력

예상 출력