Vasya 对排列多米诺骨牌很感兴趣。他厌倦了普通的多米诺骨牌,他使用不同高度的多米诺骨牌。他沿着一个轴,从左到右,在桌子上放了n张多米诺骨牌。每块多米诺骨牌都垂直于该轴,因此该轴穿过其底座的中心。第 i 个多米诺骨牌的坐标为 xi,高度为 hi。现在,Vasya 想要了解每一张多米诺骨牌,如果他将其推向右侧,将会有多少张多米诺骨牌倒下。帮助他做到这一点。
考虑一下,如果多米诺骨牌严格接触底座上方,那么它就会倒下。换句话说,初始坐标为 x、高度为 h 的多米诺骨牌倒下,会导致线段 [x + 1, x + h - 1] 上的所有多米诺骨牌倒下。
输入
第一行包含整数 n (1 ≤ n ≤ 105),它是多米诺骨牌的数量。接下来的 n 行分别包含两个整数 xi 和 hi (- 108 ≤ xi ≤ 108, 2 ≤ hi ≤ 108),它们是每个多米诺骨牌的坐标和高度。没有两块多米诺骨牌会站在一个点上。
输出
打印 n 个空格分隔的数字 zi — 如果 Vasya 将第 i 个多米诺骨牌推向右侧(包括多米诺骨牌本身),将会倒下的多米诺骨牌数量。
示例
输入 #1
4 16 5 20 5 10 10 18 2
输出 #1
3 1 4 1
输入 #2
4 0 10 1 5 9 10 15 10
输出 #2
4 1 2 1