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.