Вася увлекается расстановкой домино. Обычкновенные домино Васе надоели, и он использует костяшки разных высот. Он поставил на стол n доминошек вдоль одной оси, проходящей слева направо. Каждая доминошка стоит перпендикулярно этой оси так, что ось проходит через центр ее основания. i-ая костяшка домино имеет координату xi и высоту hi. Теперь Вася хочет узнать для каждой костяшки домино, сколько доминошек упадет, если он толкнет ее вправо. Помогите ему это сделать.
Считайте, что доминошка падает, если ее задевают строго выше основания. Другими словами, падение костяшки домино с начальной координатой x и высотой h приводит к падению всех доминошек на отрезке [x + 1, x + h - 1].
Выходные данные
Выведите n чисел zi через пробел — сколько доминошек упадет, если Вася толкнет вправо i-ую (включая ее саму).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
16 5
20 5
10 10
18 2
|
3 1 4 1
|
|
2
|
4
0 10
1 5
9 10
15 10
|
4 1 2 1
|