Штучне озеро#10154

Штучне озеро

1 секунда

128 мегабайтів

Складна

Спекотні літні дні довели невдоволення корів до небувалого рівня. Фермер Джон нарешті вирішив побудувати штучне озеро. У межах своїх інженерних досліджень він моделює озеро як двовимірний ландшафт, що складається з послідовності з $n$ суміжних рівнів, які незабаром будуть затоплені. Рівні пронумеровані від $1 \dots n$ зліва направо.

Кожен рівень $i$ описується двома цілими числами: його шириною $w_{i} (1 \leq w_{i} \leq 1000)$ w_i~(1 \le w_i \le 1000) та висотою (що представляє його відносну відмітку) $h_{i} (1 \leq h_{i} \leq 1 0^{6})$ h_i~(1 \le h_i \le 10^6). Усі висоти рівнів різні. Зліва і справа модель озера обмежена нескінченно високими стінами. Приклад профілю озера показано нижче.

         *             *  :
         *             *  :
         *             *  8
         *    ***      *  7
         *    ***      *  6
         *    ***      *  5
         *    **********  4 <- висота
         *    **********  3
         ***************  2
         ***************  1
Рівень   |  1 |2|  3   |

У моделі Фермера Джона заповнення озера починається на світанку. Вода надходить у найнижчу точку зі швидкістю $1$ квадратна одиниця води за хвилину. Вода падає вертикально вниз, поки не зустріне поверхню, після чого тече і розтікається так, як це відбувалося б зі звичайною водою. Як і в будь-якій хорошій математичній моделі, вважатимемо, що падіння і течія води відбуваються миттєво.

Визначте момент часу, в який кожен рівень виявляється покритим шаром води висотою $1$ .


ВОДА                  ВОДА ПЕРЕЛИВАЄТЬСЯ
       |                       |
     * |          *      *     |      *      *            *
     * V          *      *     V      *      *            *
     *            *      *    ....    *      *~~~~~~~~~~~~*
     *    **      *      *~~~~** :    *      *~~~~**~~~~~~*
     *    **      *      *~~~~** :    *      *~~~~**~~~~~~*
     *    **      *      *~~~~**~~~~~~*      *~~~~**~~~~~~*
     *    *********      *~~~~*********      *~~~~*********
     *~~~~*********      *~~~~*********      *~~~~*********
     **************      **************      **************
     **************      **************      **************

     Після 4 хвилин       Після 26 хвилин      Після 50 хвилин
     Рівень 1 занурено    Рівень 3 занурено    Рівень 2 занурено

Попередження: Відповідь не завжди вміщається в $32$ -бітне ціле число.

Вхідні дані

У першому рядку міститься одне ціле число $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5).

У кожному з наступних $n$ рядків міститься опис рівня $i (1 \leq i \leq n)$ i~(1 \le i \le n) — два цілих числа $w_{i}$ w_i та $h_{i}$ h_i.

Вихідні дані

Виведіть $n$ рядків. У рядку $i (1 \leq i \leq n)$ i~(1 \le i \le n) виведіть одне ціле число — кількість хвилин після світанку, через яку рівень $i$ виявляється покритим шаром води висотою $1$ .

Приклади

Приклад 1