409577: GYM103637 E Elegance in moves

Given a board of size $$$n \times m$$$ cells, you have to find the number of different pairs of cells between which the chess queen can walk in a single move and without crossing any of the given rectangles. Additionally, it is known that each cell belongs to no more than one rectangle. Recall that in a single move the queen can move any number of squares in a straight line — vertically, horizontally or diagonally.

Since the answer can be large, print it modulo $$$10^9+7$$$.

The first line contains three integers $$$n$$$ $$$m$$$ $$$k$$$ — field size and the number of rectangles, respectively. The next $$$k$$$ lines contain four integers $$$r1_i$$$ $$$c1_i$$$ $$$r2_i$$$ $$$c2_i$$$ — the coordinates of the $$$i$$$-th rectangle. No two different rectangles share a common cell.

$$$$$$ 1 \le n, m \le 10^9 $$$$$$ $$$$$$ 0 \le k \le 10^5 $$$$$$ $$$$$$ 1 \le r1_i \le r2_i \le n $$$$$$ $$$$$$ 1 \le c1_i \le c2_i \le m $$$$$$

Print a single integer, denoting the number of pairs of cells between which the chess queen can walk in a single move outside of the rectangles modulo $$$10^9+7$$$.

1 6 1
1 3 1 3

4

3 3 1
2 2 2 3

11

6 9 5
1 6 4 8
3 2 6 2
2 1 6 1
1 3 5 5
3 9 4 9

42