Magni and Modi got bored waiting for the battle with Kratos and decided to have some fun with the coloring.

The coloring looks very unusual: it is a rectangle n * m divided into nm unit squares. Coloring rows are numbered with integers from 1 to n, and columns - from 1 to m. We will denote by (a, b) the cell located at the intersection of the row with the number a and the column with the number b.

Initially, the rectangle has a checkerboard coloring, namely, the cell (a, b) is colored white if the number a + b is even, and black otherwise.

Modi loves order very much. He calls the ease of coloring the minimum number of cells that need to be recolored (that is, a black cell is made white and vice versa), so that after that it is possible to choose an integer t such that the cell (a, b) is black if a ≤ t and white otherwise. In other words, ease of coloring is the minimum number of cells whose color must be changed so that after that it is possible to draw a straight line along the side of length m, and all cells before this line are black, and after this line are white.

Magni is not so fond of order, but he loves creativity. Periodically, he repaints one of the coloring cells in the opposite color, that is, if the cell was black, it changes its color to white, and vice versa. After each such change, Modi becomes interested in what kind of ease the resulting coloring has. In total, Magni made q recolors, and on i-th of them he recolored the cell (ai, bi).

Since Magni performs his actions very quickly, Modi asked you to write a program to help him.

Input

The first line contains two integers n and m (1 ≤ n ≤ 200000, 1 ≤ m ≤ 10) - coloring dimensions. The second line contains a single integer q (1 ≤ q ≤ 200000) - the number of repaints Magni has done.

Each of the following q lines contains two integers ai and bi (1 ≤ ai ≤ n, 1 ≤ bi ≤ m) - coordinates of the cell that was repainted by the i-th action.

Output

Print q lines: for each action performed by Magni, print the ease of coloring after this action.