往届 ACM 队训练题 (参考)

1070. 染气球

单点时限: 3.0 sec

内存限制: 256 MB

小强和旺财去逛街,他们去了欧尚,旺财看见超市里面的气球兴奋的直叫,呵呵,由于小强很喜欢旺财,所以下定决心给旺财买一打回家。回家小强数了下,一共有 N 只气球,小强将 N 只气球从左到右依次编号为 1、2、3……N,每次给 2 个整数 a,b (a<=b),小强便骑上他的“小飞鸽 ” 牌电动车从气球 a 开始到气球 b 依次给每个气球涂一次颜色。但是 N 次以后小强已经忘记了第 I 个气球已经涂过几次颜色了,你能帮他算出每个气球被涂过几次颜色吗?

输入格式

每个测试实例第一行为一个整数 N,(N <= 100000). 接下来的 N 行,每行包括 2 个整数 a b(1 <= a <= b <= N)。

当 N = 0,输入结束。

输出格式

每个测试实例输出一行,包括 N 个整数,第 I 个数代表第 I 个气球总共被涂色的次数。注意,每个数据之间有个空格,最后一个数据后面没空格。

样例

Input
3
1 1
2 2
3 3
3
1 1
1 2
1 3
0
Output
1 1 1
3 2 1
不限期开放

题目列表