Robot

Time limit8sMemory limit256 MB

Summary

Count the grid cells a robot can reach from any first-row start when it moves diagonally up-left or up-right around up to 10^5 rectangular obstacles on a grid up to 10^9 by 10^9.

Level: Hard8 of 10
Topics: Sorting, Sliding window, Intervals, Implementation
Solved: No attempts yet

Problem

A robot moves on a rectangular grid with $n$ columns and $m$ rows. The robot may start in any cell of the first row. After that it makes zero or more moves. When the robot is in column $x$ and row $y$ , one move takes it to $(x+1, y+1)$ or $(x-1, y+1)$ . The robot cannot leave the grid.

The grid contains rectangular obstacles whose sides are parallel to the sides of the grid. The robot cannot enter a cell covered by an obstacle. Obstacles do not overlap, but they may touch.

Input

The first line contains $T$ , the number of test cases. Each test case starts with two integers $n$ and $m$ ( $1 \le n, m \le 10^9$ ), the number of columns and rows. The next line contains $k$ ( $1 \le k \le 10^5$ ), the number of obstacles. Each of the next $k$ lines contains four integers $x_1$ , $y_1$ , $x_2$ , $y_2$ , the coordinates of two opposite corners of an obstacle ( $1 \le x_1 \le x_2 \le n$ , $2 \le y_1 \le y_2 \le m$ ). The total number of obstacles in the input does not exceed $10^5$ .

Output

For each test case, print the number of cells the robot can visit on a separate line.

Examples1

Example 1
Input
```
1
5 7
3
2 2 4 2
1 3 1 5
2 5 3 6
```
Expected output
```
14
```