题目描述

Consider a square map with $N \times N$ cells. We indicate the coordinate of a cell by $(i,j)$, where $1 \le i,j \le N$. Each cell has a color either white or black. The color of each cell is initialized to white. The map supports the operation $\text{flip}([x_{low}, x_{high}], [y_{low}, y_{high}])$, which flips the color of each cell in the rectangle $[x_{low}, x_{high}] \times [y_{low}, y_{high}]$. Given a sequence of flip operations, our problem is to count the number of black cells in the final map. We illustrate this in the following example. Figure (a) shows the initial map. Next, we call $\text{flip}([2,4],[1,3])$ and obtain Figure (b). Then, we call $\text{flip}([1, 5], [3, 5])$ and obtain Figure (c). This map contains $18$ black cells.

:::align{center} :::

输入格式

The first line contains the number of test cases $T$ ($T \leq 10$). Each test case begins with a line containing two integers $N$ and $K$ ($1 < N,K < 10000$), where $N$ is the parameter of the map size and $K$ is the number of flip operations. Each subsequent line corresponds to a flip operation, with four integers: $x_{low}, x_{high}, y_{low}, y_{high}$.

输出格式

For each test case, output the answer in a line.

1
5 2
2 4 1 3
1 5 3 5

18