8504: 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 (ai,bi), and painted all the cells $(x,y)$ black, whereai≤x≤ai+w−1 and bi≤y≤bi+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:

(i,j)∣1≤i,j≤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), $)$ are considered 4-connected if and only if there exists a sequence of white cells c1,c2,…,ck such that:

• c_1=(i,j)c1=(i,j).
• c_k=(x,y)ck=(x,y).
• c_i and ci+1 are adjacent for all $i$ ($1\le i<k$).

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

The first line contains four integers n, m, w and h ($1\le n\le 100,000$, 1≤w,h≤m≤109), 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 ai and bi (1≤ai≤m−w+1, 1≤bi≤m−h+1), denoting a rectangle.

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

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

201