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:

<image>

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
1 1 1
1 1
 5 10 30
5 3
5 5
5 10
1 2
5 7
1 8
4 9
2 3
4 10
3 1
4 5
3 8
1 7
2 2
1 5
2 3
3 2
3 10
3 2
2 7
2 4
1 4
4 8
2 6
4 1
5 3
4 6
5 8
4 5
1 1
 3 3 10
1 2
1 3
2 2
2 2
2 2
3 2
2 2
3 2
2 3
3 1
 1 1 2
1 1
1 1

0
 399
373
355
332
306
290
261
238
233
222
207
186
180
162
140
151
144
137
144
137
111
109
91
82
77
87
78
76
83
81
 25
23
12
23
12
8
13
23
19
15
 0
1

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 5;
const long long mod = 998244353;
const double eps = 1e-10;
int n, m, q;
long long dp[maxn][maxn][2];
int vis[maxn][maxn];
long long ans;
long long dfs(int x, int y, int sgn) {
  if (dp[x][y][sgn]) return dp[x][y][sgn];
  dp[x][y][sgn] = 1;
  if (!sgn) {
    if (y < m) dp[x][y][sgn] += dfs(x, y + 1, sgn ^ 1);
  } else {
    if (x < n) dp[x][y][sgn] += dfs(x + 1, y, sgn ^ 1);
  }
  return dp[x][y][sgn];
}
void update(int x, int y, int sgn) {
  if (!vis[x][y]) {
    ans -= dp[x][y][0] + dp[x][y][1] - 1;
    dp[x][y][0] = dp[x][y][1] = 1;
    if (y < m) dp[x][y][0] += dp[x][y + 1][1];
    if (x < n) dp[x][y][1] += dp[x + 1][y][0];
    ans += dp[x][y][0] + dp[x][y][1] - 1;
  }
  if (!sgn) {
    if (x > 1) update(x - 1, y, 1);
  } else {
    if (y > 1) update(x, y - 1, 0);
  }
}
int main() {
  scanf("%d%d%d", &n, &m, &q);
  dfs(1, 1, 0);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      dfs(i, j, 0);
      dfs(i, j, 1);
      ans += dp[i][j][0] + dp[i][j][1] - 1;
    }
  }
  while (q--) {
    int x, y;
    scanf("%d%d", &x, &y);
    if (vis[x][y]) {
      dp[x][y][0] = dp[x][y][1] = 1;
      if (y < m) dp[x][y][0] += dp[x][y + 1][1];
      if (x < n) dp[x][y][1] += dp[x + 1][y][0];
      ans += dp[x][y][0] + dp[x][y][1] - 1;
      if (y > 1) update(x, y - 1, 0);
      if (x > 1) update(x - 1, y, 1);
      vis[x][y] = 0;
    } else {
      ans -= dp[x][y][0] + dp[x][y][1] - 1;
      dp[x][y][0] = dp[x][y][1] = 0;
      if (y > 1) update(x, y - 1, 0);
      if (x > 1) update(x - 1, y, 1);
      vis[x][y] = 1;
    }
    printf("%lld\n", ans);
  }
  return 0;
}
