human
Can you provide a Python code to print the number of different staircases after each query given the following:
You are given a matrix, consisting of n rows and m columns. The rows are numbered top to bottom, the columns are numbered left to right.

Each cell of the matrix can be either free or locked.

Let's call a path in the matrix a staircase if it: 

  * starts and ends in the free cell.

  * visits only free cells.

  * has one of the two following structures: 
    1. the second cell is 1 to the right from the first one, the third cell is 1 to the bottom from the second one, the fourth cell is 1 to the right from the third one, and so on.

    2. the second cell is 1 to the bottom from the first one, the third cell is 1 to the right from the second one, the fourth cell is 1 to the bottom from the third one, and so on. 


In particular, a path, consisting of a single cell, is considered to be a staircase.

Here are some examples of staircases:


Initially all the cells of the matrix are free.

You have to process q queries, each of them flips the state of a single cell. So, if a cell is currently free, it makes it locked, and if a cell is currently locked, it makes it free.

Print the number of different staircases after each query. Two staircases are considered different if there exists such a cell that appears in one path and doesn't appear in the other path.

Input

The first line contains three integers n, m and q (1 ≤ n, m ≤ 1000.
1 ≤ q ≤ 10^4) — the sizes of the matrix and the number of queries.

Each of the next q lines contains two integers x and y (1 ≤ x ≤ n.
1 ≤ y ≤ m) — the description of each query.

Output

Print q integers — the i-th value should be equal to the number of different staircases after i queries. Two staircases are considered different if there exists such a cell that appears in one path and doesn't appear in the other path.

Examples

Input

2 2 8
1 1
1 1
1 1
2 2
1 1
1 2
2 1
1 1

Output

5
10
5
2
5
3
1
0

Input

3 4 10
1 4
1 2
2 3
1 2
2 3
3 2
1 3
3 4
1 3
3 1

Output

49
35
24
29
49
39
31
23
29
27

Input

1000 1000 2
239 634
239 634

Output

1332632508
1333333000
class
assistant
#Here is Python code to print the number of different staircases after each query.
 Array2d:
    def __init__(self, n, m, arr):
        self.n = n
        self.m = m
        self.arr = arr

    @classmethod
    def full(cls, n, m, fill_value):
        return cls(n, m, [fill_value] * (n * m))

    @classmethod
    def from_list(cls, lst):
        n, m = len(lst), len(lst[0])
        arr = [lst[0]] * (n * m)
        k = 0
        for row in lst:
            for v in row:
                arr[k] = v
                k += 1
        return cls(n, m, arr)

    def _get_view(self, i, j):
        i = tuple(range(0, self.n * self.m, self.m))[i]
        j = tuple(range(self.m))[j]
        return Array2dView(self.arr, i, j)

    def get_ind(self, i, j):
        return i * self.m + j

    def __getitem__(self, index):
        try:
            return self.arr[self.get_ind(*index)]
        except TypeError:
            return self._get_view(*index)

    def __setitem__(self, index, value):
        try:
            self.arr[self.get_ind(*index)] = value
        except TypeError:
            x = self._get_view(*index)
            for i in x.i_indices:
                for j in x.j_indices:
                    self.arr[i + j] = value

    def __iter__(self):
        return iter(self.arr)

    def __reversed__(self):
        return reversed(self.arr)

    def __str__(self):
        m = max(len(str(v)) for v in self)
        res = [''] * self.n
        row = [''] * (self.m + 2)
        for i in range(self.n):
            if i == 0:
                row[0] = '['
            else:
                row[0] = ' '
            if i == self.n - 1:
                row[-1] = ']\n'
            for j in range(self.m):
                row[j + 1] = f'{str(self.arr[i * self.m + j]):>{m + 1}}'
            res[i] = ''.join(row)
        return '\n'.join(res)

    def __eq__(self, other):
        return self.arr == other.arr

    def copy(self):
        return self.__init__(self.n, self.m, self.arr[:])

    @property
    def t(self):
        arr = [self.arr[0]] * (len(self.arr))
        x = 0
        for i in range(self.n):
        ...