410771: GYM104101 D Cutting with Lines Ⅰ

There is a matrix in the 2D plane, whose vertices labelled as $$$(0,0)$$$, $$$(n, 0)$$$, $$$(0, m)$$$ and $$$(n, m)$$$.

$$$333lfy$$$ has $$$q$$$ segments. The length of the $$$i$$$-th segment is $$$a_i$$$. He wants to place these segments in this 2D plane.

There are following four ways to place the $$$i$$$-th segment:

• $$$1$$$ $$$x$$$ — The coordinates of the endpoints of the $$$i$$$-th segment are $$$(x,m)$$$ and $$$(x,m - a_i)$$$.

• $$$2$$$ $$$x$$$ — The coordinates of the endpoints of the $$$i$$$-th segment are $$$(x,\ 0)$$$ and $$$(x,\ a_i)$$$.

• $$$3$$$ $$$x$$$ — The coordinates of the endpoints of the $$$i$$$-th segment are $$$(0,\ x)$$$ and $$$(a_i,\ x)$$$.

• $$$4$$$ $$$x$$$ — The coordinates of the endpoints of the $$$i$$$-th segment are $$$(n,\ x)$$$ and $$$(n - a_i,\ x)$$$。

After placing all segments, the matrix is divided into several parts by these segments. Now please calculate the area of the largest part.

The first line of the input contains three integers $$$n, m, q$$$ $$$(1 \le n, m \le 10^6, 1 \le q \le 2000)$$$ — The size of the matrix and the number of the segments.

The next $$$q$$$ lines each line contains three integers, and the $$$i$$$-th line belong to one of the following four types:

• $$$a_i$$$ $$$1$$$ $$$x$$$$$$(0 \le x \le n,\ 1\le a_i \le 10^6)$$$ — The length of the $$$i$$$-th segment is $$$a_i$$$ and the coordinates of the endpoints are $$$(x,m)$$$ and $$$(x,m - a_i)$$$.

• $$$a_i$$$ $$$2$$$ $$$x$$$$$$(0 \le x \le n,\ 1\le a_i \le 10^6)$$$ — The length of the $$$i$$$-th segment is $$$a_i$$$ and the coordinates of the endpoints are $$$(x,\ 0)$$$ and $$$(x,\ a_i)$$$.

• $$$a_i$$$ $$$3$$$ $$$x$$$$$$(0 \le x \le m,1\le a_i \le 10^6)$$$ — The length of the $$$i$$$-th segment is $$$a_i$$$ and the coordinates of the endpoints are $$$(0,\ x)$$$ and $$$(a_i,\ x)$$$.

• $$$a_i$$$ $$$4$$$ $$$x$$$$$$(0 \le x \le m,1\le a_i \le 10^6)$$$ — The length of the $$$i$$$-th segment is $$$a_i$$$ and the coordinates of the endpoints are $$$(n,\ x)$$$ and $$$(n - a_i,x)$$$.

Print one integer — the number satisfying the conditions above.

4 7 5
2 1 1
6 3 6
2 4 3
3 3 2
3 2 2

14

The example is shown in the figure：