Fortune Telling

Time limit2sMemory limit512 MB

Summary
Given M by N cards and K rectangle flip operations, count how many cards end face up after all operations.
Level

Medium7 of 10

Topics
Sorting, Prefix sum, Implementation, Geometry
Solved
No attempts yet

Problem

Chairman K likes fortune telling and is always casting various fortunes. Today he decided to use cards to tell the fortune of the Japanese team's performance at this year's IOI. The method of telling the fortune is as follows.

  • First, lay out all the cards face up in a rectangular shape with M rows and N columns.
  • For i = 1, ..., K, perform the operation "flip over all cards located from row Ai to row Bi, counting from the top, and from column Ci to column Di, counting from the left." In other words, writing the card at row a from the top and column b from the left as (a, b), for each i the operation flips over all cards (a, b) satisfying Ai ≤ a ≤ Bi and Ci ≤ b ≤ Di.
  • After the operations finish, the result of the fortune is determined by the number of cards that are face up.

Chairman K noticed partway through that the number of card flips was far too large, so instead of actually using the cards to tell the fortune, he decided to simply find the number of cards that are face up after the operations finish.

Given the number of rows M, the number of columns N, the number of operations K, and the instructions for the K operations, write a program to find the number of cards that are face up after the operations.

Input

Read the following input from standard input.

  • The first line contains the integers M, N, K separated by spaces, indicating that the cards are laid out in M rows and N columns and that the number of operations is K.
  • Line 1 + i (1 ≤ i ≤ K) contains four integers Ai, Bi, Ci, Di (1 ≤ Ai ≤ Bi ≤ M, 1 ≤ Ci ≤ Di ≤ N), indicating that the i-th operation flips over all cards from row Ai to row Bi from the top and from column Ci to column Di from the left.

Output

Print the number of cards that are face up after the K operations on a single line to standard output.

Constraints

  • 1 ≤ M ≤ 1 000 000 000 (= 109) rows
  • 1 ≤ N ≤ 1 000 000 000 (= 109) columns
  • 1 ≤ K ≤ 100 000 (= 105) operations

Examples1

  1. Example 1

    Input
    6 5 3
2 4 1 4
4 6 3 5
1 2 3 5
    Expected output
    11