Description

N 个气球排成一排，从左到右依次编号为 1，2，3，...，N。每次给定两个整数 a，b（a ≤ b），乐乐骑上他的“小飞鸽”牌电动车，从气球 a 开始到气球 b 依次给每个气球涂一次颜色。但是 N 次以后乐乐已经忘记了第 i 个气球已经涂过几次颜色了，你能帮他算出每个气球被涂过几次颜色吗？

Format

Input

每个测试实例第一行为一个整数 N（N ≤ 100000），接下来的 N 行，每行包括 2 个整数 a，b（1 ≤ a ≤ b ≤ N）。 当 N 为 0 时，输入结束。 .

Output

每个测试实例输出一行，包括 N 个整数，第 i 个数代表第 i 个气球总共被涂色的次数。

Samples

3
1 1
2 2
3 3
3
1 1
1 2
1 3
0

1 1 1
3 2 1