We are given an array $A$ containing $n$ rows and $m$ columns, consisting of $nm$ cells that can store zeros or ones. Rows are numbered $1, \dots, n$ from top to bottom, and columns are numbered $1, \dots, m$ from left to right. The cell in the $i$-th row and $j$-th column (for $1 \le i \le n, 1 \le j \le m$) has coordinates $(i, j)$.

We can perform operations of changing (negating) numbers in a chosen rectangle on the array. Each operation is described by four numbers $i_1, j_1, i_2, j_2$. It consists of selecting the cells of the array that lie in the rectangle with opposite corners at $(i_1, j_1)$ and $(i_2, j_2)$, and then changing zeros to ones and ones to zeros in each cell of the selected rectangle.

We say an operation is simple if the top-left corner of the rectangle coincides with the top-left corner of the array (i.e., $i_1 = j_1 = 1$).

Initially, all numbers in the array are zeros. Then we perform $q$ operations that change the array. After performing each operation, we want to know how many additional simple operations we would need to perform so that all numbers in the array become zeros again.

Input

The first line of the input contains three integers $n, m$ and $q$ ($1 \le n, m \le 1000, 1 \le q \le 100\,000$) denoting the dimensions of the array and the number of operations to perform.

Each of the next $q$ lines contains a description of one operation performed on the array; the description is in the form of four integers $i_1, j_1, i_2, j_2$ ($1 \le i_1 \le i_2 \le n, 1 \le j_1 \le j_2 \le m$).

Output

The output should contain exactly $q$ lines containing the answers to the consecutive queries from the input. For the $i$-th query, you should output a single integer representing the minimum number of simple operations that must be performed so that all numbers in array $A$, modified by the first $i$ operations from the input, become zeros.

Examples

Input 1

2 3 3
1 2 2 2
1 1 2 1
1 2 1 3

Output 1

2
1
3

Subtasks

The test set is divided into the following subtasks. Tests for each subtask consist of one or more separate test groups.