Chessboard Painting

You are given a chessboard with n columns and m rows (i.e. there are \(n \times m\) cells in total). Both columns and rows are 1-indexed, so the cell in the i-th column and j-th row is denoted as \((i, j)\). Initially, all cells are white.

You are then given \(q\) painting operations. There are three types of operations:

1. Horizontal line painting: Given two cells \((x_1,y_1)\) and \((x_2,y_2)\) with \(x_1 \le x_2\) and \(y_1 = y_2\), paint all cells in row \(y_1\) from column \(x_1\) to column \(x_2\) (inclusive) black.
2. Vertical line painting: Given two cells \((x_1,y_1)\) and \((x_2,y_2)\) with \(x_1 = x_2\) and \(y_1 \le y_2\), paint all cells in column \(x_1\) from row \(y_1\) to row \(y_2\) (inclusive) black.
3. Diagonal line painting: Given two cells \((x_1,y_1)\) and \((x_2,y_2)\) with \(x_1 \le x_2\) and \(x_2-x_1 = y_2-y_1\), paint all cells \((x_1+i, y_1+i)\) for \(0 \le i \le x_2-x_1\) black. Note: This operation will appear at most 5 times.

Your task is to compute the total number of black cells on the board after all \(q\) operations have been performed. If a cell is painted multiple times, it is counted only once.

Input/Output: See below.

inputFormat

The first line contains three integers \(n\), \(m\), and \(q\) representing the number of columns, the number of rows, and the number of operations respectively.

The next \(q\) lines each contain four integers \(x_1\), \(y_1\), \(x_2\), \(y_2\). It is guaranteed that for a horizontal painting operation, \(y_1=y_2\) and \(x_1 \le x_2\); for a vertical painting operation, \(x_1=x_2\) and \(y_1 \le y_2\); and for a diagonal painting operation, \(x_2-x_1=y_2-y_1\) and \(x_1 \le x_2\).

outputFormat

Output a single integer, the number of black cells on the board after all operations.

sample

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

7