Description

有一家大型酒店，从开业至今有N名客人入住，编号分别为1到n。酒店详细登记了每一位客人的入住信息，信息表明第i位客人从第A_i天开始连续入住了B_i天，即该客人的入住时间包含第A_i天、第A_i+1天、... 第A_i+B_i-1天。 请分别计算恰好有1名客人，2名客人，...N名客人入住酒店的天数。

Format

Input

每行包含一个整数N，表示入住酒店的客人数量； 接下来N行，每行包含两个整数A_i，B_i，整数之间以一个空格隔开，表示第i位客人的入住信息。

Output

一行包含N个整数，分别表示恰好有1名客人，2名客人，...N名客人入住酒店的天数，整数之间以一个空格隔开。

Samples

4
1 2
2 2
2 3
3 3

2 1 2 0

Limitation

数据范围： 测试点1~10:1<=N<=2*10⁵,1<=A_i,Bⁱ<=10⁹。