The Ideal City

Like many Italian scientists and artists of his time, Leonardo da Vinci was deeply interested in city planning and design. He wanted to design an ideal city: comfortable, making generous and rational use of space, and far from the cramped, stifling feel of a medieval town.

A city is built by placing $N$ blocks on an infinite grid of square cells. Each cell is identified by a (row, column) coordinate pair. The cells adjacent to cell $(i, j)$ are $(i-1, j)$, $(i+1, j)$, $(i, j-1)$, and $(i, j+1)$. Each block covers exactly one cell and may only be placed on a cell $(i, j)$ with $1 \le i, j \le 2^{31} - 2$. Two blocks placed on adjacent cells are said to be adjacent.

In an ideal city every block is connected, with no holes. Formally, the following two conditions must hold.

1. For any two empty cells, there is at least one path from one to the other that moves only through adjacent empty cells.
2. For any two non-empty cells, there is at least one path from one to the other that moves only through adjacent non-empty cells.

(None of the figures below is an ideal city. The first two violate condition 1, the third violates condition 2, and the fourth violates both.)

A single step inside the city moves from one block to an adjacent block; you cannot step onto an empty cell. Let $v_0, v_1, \dots, v_{N-1}$ be the coordinates of the $N$ blocks. For two distinct blocks $v_i$ and $v_j$, the distance $d(v_i, v_j)$ is the minimum number of steps needed to travel from one to the other.

The figure below shows an ideal city of $N = 11$ blocks with coordinates $v_0=(2,5)$, $v_1=(2,6)$, $v_2=(3,3)$, $v_3=(3,6)$, $v_4=(4,3)$, $v_5=(4,4)$, $v_6=(4,5)$, $v_7=(4,6)$, $v_8=(5,3)$, $v_9=(5,4)$, $v_{10}=(5,6)$. Here $d(v_1, v_3)=1$, $d(v_1, v_8)=6$, $d(v_6, v_{10})=2$, and $d(v_9, v_{10})=4$.

You must compute the sum of the distances over every pair of blocks $v_i$, $v_j$ with $0 \le i < j \le N-1$, that is $$\sum_{0 \le i < j \le N-1} d(v_i, v_j).$$ The city above has $11 \times 10 / 2 = 55$ pairs of blocks, and the sum of the distances over all pairs is $174$.

Because the result can be very large, output the sum modulo 1,000,000,000.

The first line contains the number of blocks $N$. Each of the next $N$ lines contains the coordinates $X_i$ and $Y_i$ of block $i$, separated by a space ($1 \le X_i, Y_i \le 2^{31} - 2$). The given city is guaranteed to be an ideal city.

Print, on a single line, the sum of the distances over all pairs of blocks with $0 \le i < j \le N-1$, taken modulo 1,000,000,000.