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[^1], na ktorý sa bude pozerať aj sám cézar. Na začiatku dostane každý gladiátor 1 bitkoin[^2] 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.

1. To znamená, že súboj pokračuje, dokým jeden z dvojice nezomrie↩

2. bitkoin – drobná zlatá minca používaná medzi bitkármi (odtiaľ názov)↩