На игралишту се свашта дешава. Како би клан из суседног игралишта могао сваког тренутка да лансира напад, мора да постоји јасна подела улога међу децом. Због тога, свако игралиште мора да има свог председника, потпредседника, шмекера, голмана и благајника.

Док се остале улоге бирају традиционалним демократским путем, улога дежурног шмекера, која је, свакако, по много чему посебна, има и посебан начин избора. Наиме, игралиште можемо замислити као координатну раван. Како на игралишту постоје стриктна правила понашања, свако дете ће доћи директно на своју предодређену позицију \((x,y)\), и остатак дана се одатле неће померати (немојте да бринете, сваком детету је обезбеђена лична љуљашка и пар кликера да му не би било досадно). Шмекер је неко ко је увек у центру пажње, па тај једино може бити дете са позицијом на координатама \((x_s,y_s)\) тако да важи следеће:

• Број деце на игралишту са координатама \((x,y)\), где је \(x>x_s\) и \(y>y_s\) је једнак броју деце на игралишту са координатама \((x,y)\), где је \(x<x_s\) и \(y<y_s\);
• Број деце на игралишту са координатама \((x,y)\), где је \(x>x_s\) и \(y<y_s\) је једнак броју деце на игралишту са координатама \((x,y)\), где је \(x<x_s\) и \(y>y_s\).

На почетку је игралиште празно и на њега редом долазе деца. У \(i\)-том минуту ће \(i\)-то дете стићи на своју позицију \((x_i,y_i)\). Председник игралишта вас је замолио да праведно регулишете доделу улоге шмекера, тако што после сваког новог доласка детета предложите кандидата који испуњава услове, или да кажете уколико такав не постоји.

Опис улаза

У првој линији стандардног улаза се налази позитиван цео број \(N\), укупан број деце. У \(i\)-том од наредних \(N\) редова се налазе по \(2\) цела броја \(x_i\) и \(y_i\), која представљају позицију \(i\)-тог детета, које ће доћи на игралиште у \(i\)-том минуту. ## Опис излаза На стандардни излаз потребно је исписати \(N\) линија. У \(i\)-тој линији је потребно исписати индекс неког детета које може бити шмекер (уколико их има више, исписати било које), а уколико такво не постоји, потребно је исписати \(-1\). ## Ограничења - \(1\leq N \leq 200.000\) - \(1 \leq x_i,y_i \leq 1.000.000.000\) - Све вредности \(x_i\) су међусобно различите - Све вредности \(y_i\) су међусобно различите ## Подзадаци 1. (12 поена) \(N\leq500\) 2. (22 поена) \(x_i=y_i\) 3. (23 поена) \(N\leq4.000\) 4. (43 поена) Без додатних ограничења

Примери

Пример 1

Улаз

3
1 1
2 2
3 3

Излаз

1
-1
2

Објашњење

После прве минуте ће се на игралишту налазити само једно дете, тако да ће бити по \(0\) деце у сваком од четири посматрана скупа, па ће он моћи да буде шмекер. После другог минута ће на игралишту бити \(2\) детета, и ниједан неће моћи да буде шмекер. После трећег минута, дете број \(2\) може да буде шмекер јер има по \(1\) дете чије су обе координате веће/мање, док је ових “мешовитих” по \(0\). ### Пример 2

Улаз

5
1 1
2 5
3 3
4 2
5 4

Излаз

1
-1
-1
-1
3

Објашњење

После 5 минута, за дете број \(3\) су сва \(4\) скупа величине \(1\), па он може да буде шмекер.