마을 최고령자

아주 먼 옛날, Stackköping이라는 작은 마을이 있었다. Stackköping 주민들에게는 몇 가지 특별한 전통이 있었다. 한 전통은 매년 말에 살아 있는 주민 중 가장 나이가 많은 사람이 신년 연설을 해야 한다는 것이었다. 또 다른 전통은 매년 새로 태어날 수 있는 사람이 최대 한 명이라는 것이었으며, 일부 전문가에 따르면 이것이 결국 Stackköping의 몰락을 초래했다.

고고학 발굴 중 Stackköping에서 지금까지 살았던 $n$명 모두의 출생 연도와 사망 연도가 기록된 문서가 발견되었다. 당신은 이 문서를 입수했고, 각 사람이 신년 연설을 몇 번 했는지 계산하려 한다.

신년 연설은 항상 매년 일어나는 일 중 가장 마지막에 이루어지므로, 같은 해에 이루어지는 신년 연설 이후에는 아무도 태어나거나 죽지 않는다. 새해를 맞을 때 살아 있는 사람이 아무도 없다면 당연히 연설도 전혀 이루어지지 않는다. 그렇지 않으면 살아 있는 사람이 단 한 명뿐이더라도 항상 연설이 이루어진다.

점수

제출한 풀이는 여러 테스트 케이스 그룹으로 평가된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

$1$ |$30$| $1 \le n \le 1000$

$2$ |$25$| 모든 사람이 같은 기간 동안 살았으며, $f_i, d_i \le 3\cdot 10^5$

$3$ |$45$| 추가 제한 없음

첫째 줄에 사람의 수를 나타내는 정수 $n$이(가) 주어진다($1 \le n \le 10^5$). 이어지는 $n$개의 줄에는 두 정수 $f_i$와(과) $d_i$이(가) 주어진다($0 \le f_i < d_i \le 10^9$). 이는 각각 $i$번 사람이 태어난 연도와 사망한 연도이다. 모든 수 $f_i$은(는) 서로 다르다.

각 줄에 정수 하나씩 $n$개의 줄을 출력한다. 이때 $i$번째 수는 $i$번째 사람이 신년 연설을 한 횟수이다.