Artwork

A template for an artwork is a white grid of n × m squares. The artwork will be created by painting q horizontal and vertical black strokes. A stroke starts from square (x₁,y₁), ends at square (x₂,y₂) (x₁ = x₂ or y₁ = y₂), and changes the color of all squares (x,y) to black where x₁ ≤ x ≤ x₂ and y₁ ≤ y ≤ y₂.

The beauty of an artwork is the number of regions in the grid. Each region consists of one or more white squares that are connected to each other using a path of white squares in the grid, walking horizontally or vertically, but not diagonally. The initial beauty of the artwork is 1. Your task is to calculate the beauty after each new stroke. Figure 1 illustrates how the beauty of the artwork varies in the Sample Input.

Figure 1: Illustration of the Sample Input.

Input Specification

The first line of the input contains three integers n, m, and q (1 ≤ n, m ≤ 1000, 1 ≤ q ≤ 10⁴).

Then follow q lines that describe the strokes. Each line consists of four integers x₁, y₁, x₂, and y₂ (1 ≤ x₁ ≤ x₂ ≤ n, 1 ≤ y₁ ≤ y₂ ≤ m). Either x₁ = x₂ or y₁ = y₂ (or both).

Output Specification

For each of the q strokes, output a line containing the beauty of the artwork after the stroke.

Sample Input

1. 4 6 5
2. 2 2 2 6
3. 1 3 4 3
4. 2 5 3 5
5. 4 6 4 6
6. 1 6 4 6

download as text file

Output for Sample Input

1. 1
2. 3
3. 3
4. 4
5. 3

download as text file