Corners of Polygon
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