Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.

Béla egyszerű dartsot játszik, ahol a tábla egy xy sík, amelyen néhány (gyakorlatilag sok) úgynevezett „ellenőrzőpont” található (x1,y1), (x2,y2), egész számú koordinátákkal.


Erre a dartsra külön szabályok vonatkoznak! Az ellenőrzőpontok száma legyen N. Béla eldobja a nyilat, és ha az (xA,yA) koordinátán találja el a síkot, akkor az alábbi módon tudjuk kiszámolni, hogy hány pontot szerzett: - Ha minden (xi,yi) ellenőrzőpontra érvényes, hogy xixA, Béla 0 pontot kap; - Ha minden (xi,yi) ellenőrzőpontra érvényes, hogy yiyA, Béla 0 pontot kap; - Egyébként (vagyis, ha az ellenőrzőpontok között van legalább egy, amelynek az x koordinátája egyenlő xA-val, és van legalább egy, amelynek az y koordinátája egyenlő yA-val) Béla által megszerzett pontokat az alábbi képlettel tudjuk kiszámolni:


i=1N|xixA||yiyA|


Adott egy M pontot tartalmazó sorozat, ahol a pontok koordinátái (x1,y1), (x2,y2), (xM,yM) egész számok. Minden i=1,2,,M-re ki kell íratni, hogy Béla legtöbb hány pontot tud szerezni egy dobással, abban az esetben, ha az ellenőrzőpontok halmaza csak az első i pontját tartalmazza ezen sorozatnak. Az eredményt 109+7 modulóval kell kiíratni.


A bemenet leírása


A szabványos bemenet első sorában az M egész szám áll ‒ a sorozatban szereplő összes pont száma.

A következő M sorban szóközzel elválasztott egész számpárok állnak, amelyek az xi,yi pontok koordinátáit jelölik.


A kimenet leírása


Az M sorban rendre kiíratni az R1,R2,...,RM számokat, ahol Ri a lehető legmagasabb pontszám 109+7 modulóval, amelyet Béla be tud gyűjteni, amennyiben az ellenőrzőpontok halmaza kizárólag a sorozat első i elemét tartalmazza.


1. példa


Bemenet


3
2 1
1 2
3 3


Kimenet


0
1
4


A példa magyarázata


Ha csak az első pont ellenőrzőpont, 0 pont jár, bárhova is talál be a nyíl. Amennyiben az első két pont az ellenőrzőpont, eltalálhatjuk az (1,2)-t, és az alábbi pontszámot kapjuk: 11+00=1, amennyiben mindhárom pont ellenőrzőpont, akkor optimális az (1,1) pont, ahol 10+01+22=4 pontszámot kapunk.


2. példa


Bemenet


4
1 2
2 1
5 4
3 5


Kimenet


0
1
17
24


Korlátozások



A tesztpéldák hat diszjunkt csoportba vannak sorolva: