Lago artificiale#10154

Lago artificiale

1 secondo

128 megabyte

Difficile

Le calde giornate estive hanno portato il malcontento delle mucche a un livello senza precedenti. L'agricoltore John ha finalmente deciso di costruire un lago artificiale. Nell'ambito dei suoi studi ingegneristici, modella il lago come un paesaggio bidimensionale composto da una sequenza di $n$ livelli adiacenti, che presto verranno sommersi. I livelli sono numerati da $1 \dots n$ da sinistra a destra.

Ogni livello $i$ è descritto da due numeri interi: la sua larghezza $w_{i} (1 \leq w_{i} \leq 1000)$ w_i~(1 \le w_i \le 1000) e la sua altezza (che rappresenta la sua quota relativa) $h_{i} (1 \leq h_{i} \leq 1 0^{6})$ h_i~(1 \le h_i \le 10^6). Tutte le altezze dei livelli sono distinte. A sinistra e a destra il modello del lago è delimitato da pareti infinitamente alte. Un esempio di profilo del lago è mostrato di seguito.

         *             *  :
         *             *  :
         *             *  8
         *    ***      *  7
         *    ***      *  6
         *    ***      *  5
         *    **********  4 <- altezza
         *    **********  3
         ***************  2
         ***************  1
Livello  |  1 |2|  3   |

Nel modello dell'agricoltore John, il riempimento del lago inizia all'alba. L'acqua arriva nel punto più basso a una velocità di $1$ unità quadrata di acqua al minuto. L'acqua cade verticalmente verso il basso finché non incontra una superficie, dopodiché scorre e si distribuisce come farebbe l'acqua normale. Come in ogni buon modello matematico, assumiamo che la caduta e il flusso dell'acqua avvengano istantaneamente.

Determinate il momento in cui ogni livello risulta coperto da uno strato d'acqua di altezza $1$ .


ACQUA                 L'ACQUA TRABOCCA
       |                       |
     * |          *      *     |      *      *            *
     * V          *      *     V      *      *            *
     *            *      *    ....    *      *~~~~~~~~~~~~*
     *    **      *      *~~~~** :    *      *~~~~**~~~~~~*
     *    **      *      *~~~~** :    *      *~~~~**~~~~~~*
     *    **      *      *~~~~**~~~~~~*      *~~~~**~~~~~~*
     *    *********      *~~~~*********      *~~~~*********
     *~~~~*********      *~~~~*********      *~~~~*********
     **************      **************      **************
     **************      **************      **************

     Dopo 4 minuti        Dopo 26 minuti       Dopo 50 minuti
     Il livello 1 è       Il livello 3 è       Il livello 2 è
     sommerso             sommerso             sommerso

Attenzione: La risposta non sempre rientra in un intero a $32$ bit.

Input

La prima riga contiene un unico numero intero $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5).

Ciascuna delle successive $n$ righe contiene la descrizione del livello $i (1 \leq i \leq n)$ i~(1 \le i \le n) — due numeri interi $w_{i}$ w_i e $h_{i}$ h_i.

Output

Stampate $n$ righe. Nella riga $i (1 \leq i \leq n)$ i~(1 \le i \le n) stampate un unico numero intero — il numero di minuti dopo l'alba trascorsi i quali il livello $i$ risulta coperto da uno strato d'acqua di altezza $1$ .

Esempi

Esempio 1