7. Utrápený Michallius

Každý dobre vie, že Michallius sa rád bije. Chcel sa prihlásiť na bitkársky turnaj konajúci sa na konci semestra, zaškrtol však zlú kolónku a ocitol sa na prestížnom gladiátorskom deathmatch-i¹, na ktorý sa bude pozerať aj sám cézar. Na začiatku dostane každý gladiátor 1 bitkoin² a za porazenie súpera získava všetky jeho bitkoiny. Takže gladiátori sa vedia pekne nabaliť. Bojuje sa v dvoch typoch súbojov: v boji s mečom a boji s kopijou. Na začiatku súboja sa vždy vyberie typ zbrane a táto zbraň sa počas súboja nezmení.

Chudák Michallius bol sprvu veľmi utrápený a bál sa. Kašľal na svoj bitkoin, chcel iba prežiť. Musel preto teda niečo robiť. Rozhodol sa preskúmať svoje sily a sily ostatných súperov. O každom gladiátorovi (vrátane seba) si poznačil jeho silu s mečom a s kopijou. Robil to dôkladne, žiadni dvaja bojovníci nemajú rovnakú silu v jednom type boja. Michallius cez skúškové trénoval, poctivo posilňoval, a aj sa správne stravoval. Zistil, že nakoniec je v tom bojovaní celkom dobrý, preto ho už začína zaujímať koľko by si vedel maximálne odniesť z tohto turnaja.

Zistite, aký maximálny zárobok si vie Michallius odniesť. A vlastne, keď už to zistíte o Michalliovi, zistite to isté o každom ďalšom gladiátorovi.

Úloha

Na turnaj sa prihlásilo \(n\) gladiátorov. O každom gladiátorovi vieme jeho silu v boji s mečom a silu v boji s kopijou (obe tieto sily sú celé čísla). Každý gladiátor dostane na začiatku 1 bitkoin. Turnaj má pomerne voľnú štruktúru, ktorá vyzerá nasledovne:

1. Vylosujú sa dvaja gladiátori, ktorí ešte neprehrali.
2. Vylosuje sa, či budú bojovať s kopijami, alebo s mečmi.
3. Pobijú sa. Gladiátor, ktorý je v danom type boja silnejší, zvíťazí.
4. Víťaz získa všetky bitkoiny porazeného a porazený vypadáva z turnaja (z pochopiteľných dôvodov).

Tieto štyri kroky sa opakujú, až kým turnaj cézara neomrzí. Môže sa tak stať, že na konci prežije viacero gladiátorov.

Chceme vedieť o každom gladiátorovi, koľko bitkoinov môže na turnaji maximálne zarobiť, ak by všetky losovania dopadli preňho najlepším možným spôsobom.

Formát vstupu

Na prvom riadku vstupu sa nachádza celé číslo \(n\) – počet gladiátorov na turnaji. Platí: \(1 \leq n \leq 100,000\). Nasleduje \(n\) riadkov. V \(i\)-tom riadku sa nachádzajú dve celé čísla oddelené medzerou: sila \(i\)-teho gladiátora v boji s mečom \(m_i\) a jeho sila v boji s kopijou \(k_i\). Platí \(1 \leq m_i , k_i \leq n\). Môžete predpokladať, že žiadni dvaja gladiátori nemajú rovnakú silu s mečom, ani rovnakú silu s kopijou.

Formát výstupu

Vypíšte \(n\) riadkov. V \(i\)-tom riadku vypíšte počet bitkoinov, ktoré môže \(i\)-ty gladiátor získať.

Príklady

Input:

4
2 3
3 2
1 1
4 4

Output:

3
3
1
4

Michallius (prvý gladiátor) dokáže poraziť druhého gladiátora ak budú bojovať s kopijou, tretieho v ľubovolnom boji. Druhý gladiátor porazí Michallia v boji s mečom a tretieho v ľubovolnom boji. Tretí gladiátor je bezmocná ovca, a štvrtý je Spartakus.

Input:

4
3 3
4 1
1 4
2 2

Output:

4
4
4
4

Všimnime si, že posledný gladiátor dokáže získať aj Michalliov bitkoin, hoci je slabší v oboch typoch boja.