D. Cutting with Lines Ⅰ
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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)$$$.
Output

Print one integer — the number satisfying the conditions above.

Example
Input
4 7 5
2 1 1
6 3 6
2 4 3
3 3 2
3 2 2
Output
14
Note

The example is shown in the figure：