题目描述

译自 COCI 2022/2023 Contest #2 T3「Lampice」

圣诞节要来了！Teo 决定装饰他的阳台。

他有一个很大的矩形阳台。阳台 $n$ 米长 $m$ 米宽。Teo 准备用一种奇怪的方式装饰阳台。他准备把圣诞彩灯放满阳台，而不是只放在角落里。

Teo 有 $2k$ 盏灯，这些灯共有 $k$ 种颜色，每种颜色都有两盏灯。他会把它们放在 $(x_i, y_i)$ 位置，其中 $x_i$ 是到阳台左边的距离，$y_i$ 是到阳台底部的距离。

他对他装饰阳台的方法十分自豪，所以他决定给自己放大镜。但是不一会儿他就觉得太闲了，所以他返回了阳台。他开始数阳台上有多少好的矩形。如果对于所有颜色，是这种颜色的灯都在这个矩形里或都在矩形外，这个矩形就是好的。如果灯位于矩形的一条边上，则认为灯位于矩形内部。

Teo 意识到数好矩形不是一个简单的工作。他想知道有多少顶点到阳台左边和下边的距离都是整数的好矩形。我们考虑的所有矩形的边都与阳台的边平行。这就是你的任务了！数出好矩形的个数。

输入格式

第一行三个整数 $n, m, k$ ($1 \le n \le 150$, $1 \le m \le 1000$, $0 \le k \le 200000$)，分别表示阳台的长宽和灯的颜色种类数。

接下来 $k$ 行，每行四个整数 $x_1, y_1, x_2, y_2$ ($0 \le x_1, x_2 \le n$, $0 \le y_1, y_2 \le m$)，表示颜色为 $i$ 的第一盏灯和第二盏灯的位置。

输出格式

输出一行一个整数，表示好矩形的个数。

2 2 1
0 0 1 2

3

3 3 0

36

3 3 5
0 0 0 0
0 0 1 3
0 0 3 1
1 3 3 1
1 3 3 1

7

数据规模与约定

子任务编号 附加限制 分值

1. 对于每种颜色的灯，$x_1 = y_1 = 0$ 24

2. $n, m \le 10$，$k \le 1000$ 11

3. $m \le 150$ 32

4. 无附加限制 33