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

Бане игра једноставни пикадо који је организован тако да је табла стандардна \(xy\) раван са неколико (коначно много) такозваних “контролних тачака” \((x_1, y_1)\), \((x_2, y_2)\), \(\ldots\) са целобројним координатама.


За овај пикадо важе посебна правила! Нека је број контролних тачака \(N\). Бане ће бацити стрелицу и уколико та стрелица погоди раван у тачки са координатама \((x_A, y_A)\), тада Бане осваја поенe на следећи начин: - Ако за сваку контролну тачку \((x_i, y_i)\) важи да је \(x_i \neq x_A\), Бане осваја 0 поена; - Ако за сваку контролну тачку \((x_i, y_i)\) важи да је \(y_i \neq y_A\), Бане осваја 0 поена; - Иначе (тј. ако међу контролним тачкама постоји бар једна са \(x\) координатом једнаком \(x_A\) и бар једна са \(y\) координатом једнаком \(y_A\)) број поена које Бане осваја је једнак


\[\sum_{i=1}^{N}|x_i-x_A|\cdot|y_i-y_A|\]


Дат је низ од \(M\) тачака са целобројним координатама \((x_1, y_1)\), \((x_2, y_2)\), \(\ldots\) \((x_M, y_M)\). За свако \(i = 1,2, \ldots, M\) исписати који је највећи број поена који Бане може да добије у једном бацању уколико скуп контролних тачака садржи само првих \(i\) тачака овог низа. Резултате исписивати по модулу \(10^9 + 7\).


Опис улаза


У првој линији улаза налази се цео број \(M\) - укупан број тачака у низу

У наредних \(M\) линија налазе се парови целих бројева одвојених размаком који представљају координате тачака \(x_i, y_i\)


Опис излаза


У \(M\) линија исписати бројеве \(R_1, R_2, ..., R_M\), редом, где је \(R_i\) највећи могући број поена по модулу \(10^9 + 7\) који Бане може освојити ако скуп контролних тачака садржи искључиво првих \(i\) тачака из низа.


Пример 1


Улаз


3
2 1
1 2
3 3


Излаз


0
1
4


Објашњење примера


Ако је контролна само прва тачка, где год да стрелица погоди, добија се \(0\) поена. Ако су нам контролне прве две тачке можемо “погодити” \((1, 2)\), и добити резултат \(1\cdot1+0\cdot0=1\), а ако су све три тачке, оптимална је тачка \((1, 1)\), где је резултат \(1\cdot 0+0\cdot 1+2\cdot 2=4\).


Пример 2


Улаз


4
1 2
2 1
5 4
3 5


Излаз


0
1
17
24


Ограничења



Тест примери су подељени у шест дисјунктних група: