cho.sh

Folded Paper Painting

Simulate K rounds of folding a W by H rectangle along a vertical line and several horizontal folds, painting one rectangle each round through all layers, and report the unpainted area at the end.

Hard9GeometrySimulationImplementationDivide and conquerNo attempts yetTime limit2sMemory limit128 MB

Problem

Jimin has a rectangular sheet of paper with width W and height H. Jimin will repeat the following painting process K times. For the i-th process, where 0 <= i < K, do the following:

  1. Fold the paper along the line x = f[i]. The part on the left is folded onto the part on the right.
  2. Divide the current paper horizontally into c[i] + 1 intervals of equal height, then fold it c[i] times, starting from the uppermost interval and proceeding downward.
  3. In the current folded state, take the lower-left point of the folded paper as (0, 0). Paint the rectangle whose lower-left corner is (x1[i], y1[i]) and whose upper-right corner is (x2[i], y2[i]). The paint soaks through every overlapping layer of paper.
  4. Unfold the paper.

After all processes are complete, find the area that is still unpainted.

Input

The first line contains three integers W, H, and K.

Each of the next K lines contains six integers f[i], c[i], x1[i], y1[i], x2[i], and y2[i], describing one folding and painting process.

Output

Print the area of the unpainted region.

Constraints

  • 1 <= W, H <= 10^9
  • 1 <= K <= 50
  • 0 <= f[i] <= W
  • 0 <= c[i] <= 1,000
  • c[i] + 1 is a divisor of H
  • 0 <= x1[i] < x2[i] <= max(f[i], W - f[i])
  • 0 <= y1[i] < y2[i] <= H / (c[i] + 1)