Shallow Moon

There are $m \times m$ cells on a grid, the top-left cell is at $(1,1)$ while the bottom-right cell is at $(m,m)$. Initially, all the cells were colored white. Little Q has drawn $n$ black $w\times h$ rectangles on the grid. For the $i$-th rectangle, Little Q chose a cell at $(a_i,b_i)$, and painted all the cells $(x,y)$ black, where $a_i\leq x\leq a_i+w-1$ and $b_i\leq y\leq b_i+h-1$.

After Little Q finished all of his work, he is now wondering how many pairs of white cells are 4-connected. Please write a program to calculate:
$$\sum_{(i,j)|1\leq i,j\leq m,\ (i,j)\ is\ white}f(i,j)$$Here $f(i,j)$ is the number of white cells that are 4-connected with $(i,j)$, including $(i,j)$ itself.

Two cells are considered adjacent if and only if they share a common side. Two white cells $(i,j)$, $(x,y)$ are considered 4-connected if and only if there exists a sequence of white cells $c_1,c_2,\dots,c_k$ such that:

- $c_1=(i,j)$.
- $c_k=(x,y)$.
- $c_i$ and $c_{i+1}$ are adjacent for all $i$ ($1\leq i < k$).

The first line contains a single integer $T$ ($1 \leq T \leq 1\,000$), the number of test cases. For each test case:

The first line contains four integers $n$, $m$, $w$ and $h$ ($1 \leq n \leq 100\,000$, $1\leq w,h\leq m\leq 10^9$), denoting the number of rectangles, the size of the grid, and the size of each rectangle.

Each of the next $n$ lines contains two integers $a_i$ and $b_i$ ($1\leq a_i\leq m-w+1$, $1\leq b_i\leq m-h+1$), denoting a rectangle.

It is guaranteed that the sum of all $n$ is at most $2\,000\,000$.

For each test case, print a single line containing an integer denoting the answer. Note that the answer may be extremely large, so please print it modulo $2^{64}$ instead.

1
4 6 2 2
1 3
2 2
3 5
4 1

201

2022“杭电杯”中国大学生算法设计超级联赛（3）