Corners of Polygon


Submit solution

Points: 1 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

An is learning to color and study geometry.

In the first exercise, An colors on a piece of paper divided into \(M\) rows and \(N\) columns. The cell at row \(i\) and column \(j\) is denoted as \((i, j)\). Following the teacher's instructions, An needs to color \(Q\) rectangles. The \(i\)-th rectangle has its top-left cell at \((x_i, y_i)\) and bottom-right cell at \((u_i, v_i)\). An colors all the cells in this rectangle blue (because An likes red).

In the second exercise, the teacher asks An to count the number of vertices (corners) of the polygon formed by all the colored cells combined. The problem guarantees that all colored cells form a single connected polygon. Because the figure is too chaotic, An needs to count very carefully. The teacher is also quite confused by this drawing, so she needs your help!

Input

  • The first line contains three integers \(M, N, Q \ (1 \le M, N, Q \le 1000)\);
  • The next \(Q\) lines contain four integers \(x_i, y_i, u_i, v_i \ (1 \le x_i \le u_i \le M; 1 \le y_i \le v_i \le N)\).

Output

  • A single integer representing the number of vertices of the resulting polygon.

Examples

Sample 1

input

6 6 1
1 1 3 4

output

4
Sample 2

input

10 10 2
2 2 5 6
4 4 6 9

output

8
Sample 3

input

10 10 5
2 3 3 8
2 3 8 4
7 3 8 8
2 7 8 8
4 6 4 6

output

10
Sample 4

input

10 10 3
2 6 8 6
3 5 3 7
4 4 5 8

output

16

Comments

There are no comments at the moment.