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

Bane is playing a simple darts game, in which the board is the usual x-y plane with a few (finitely many) “control points” $$(x_1,y_1)$$, $$(x_2, y_2)$$, $$\dots$$. The coordinates of control points are integers.

This game has special rules: let the number of control points be $$N$$. If Bane throws a dart that lands at the point $$(x_A, y_A)$$, he scores points in the following ways:

• If for all control points $$(x_i, y_i)$$ we have $$x_i \neq x_A$$, he scores 0 points.

• If for all control points $$(x_i, y_i)$$ we have $$y_i \neq y_A$$, he scores 0 points.

• Otherwise (if the x-coordinate matches at least one control point, and the y-coordinate matches at least one control point), he scores the following number of points:

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

You are given $$M$$ points with integer coordinates $$(x_1, y_1)$$, $$(x_2, y_2)$$, …, $$(x_m, y_m)$$. For each $$i = 1, 2, \dots, M$$, you should find the largest number of points Bane can score with a single thrown dart, if the set of control points is exactly the first $$i$$ given points.

The answers should be printed modulo $$10^9 + 7$$.

## Input format

The first line of standard input contains an integer $$M$$: the number of points in the array.

The following $$M$$ lines contain two integers each: the coordinates $$x_i, y_i$$ of each point.

## Output format

Your program should print $$M$$ lines to the standard output, where the $$i$$-th line contains the largest possible score Bane can get with a single dart throw if the control points are the first $$i$$ points in the given list, modulo $$10^9 + 7$$.

## Sample 1

### Input

3
2 1
1 2
3 3

### Output

0
1
4

## Explanation

If the only control point is the first point, Bane will score zero points regardless of where he throws the dart. With two control points, the highest-scoring throw woud be $$(1, 2)$$, for $$1 \cdot 1 + 0 \cdot 0 = 1$$ points. With three, the optimal throw is $$(1, 1)$$, scoring $$1 \cdot 0 + 0 \cdot 1 + 2 \cdot 2 = 4$$ points.

## Sample 2

### Input

4
1 2
2 1
5 4
3 5

### Output

0
1
17
24

## Constraints

• $$1 \leq M \leq 10^6$$
• $$|x_i|, |y_i| \leq 10^5$$

Testcases are split into six disjoint groups:

• In tests worth 10 points: $$1 \leq M \leq 100$$
• In tests worth 10 points: $$1 \leq M \leq 500$$
• In tests worth 15 points: $$1 \leq M \leq 2000$$
• In tests worth 15 points: $$1 \leq M \leq 2\cdot 10^5$$
• In tests worth 10 points: $$1 \leq M \leq 10^5$$ и $$0 \leq x_i, y_i \leq 10$$
• In tests worth 40 points: no additional constraints.