#include <bits/stdc++.h>
using namespace std;
long long t = 1, n, m, k, q, l, r, ans, a[1009][1009], dy[1009][1009],
          xy[1009][1009], zt[1009][1009], b, c, u, v, x, y, z, mod = 1e9 + 7;
string s;
struct st {
  long long x, y;
};
bool cmp(const st &a, const st &b) { return a.x < b.x; }
inline long long read() {
  long long s = 0, w = 1;
  char ch = getchar();
  while (ch > '9' || ch < '0') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch <= '9' && ch >= '0')
    s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
  return s * w;
}
long long qp(long long x, long long y) {
  long long a = 1, b = x;
  while (y) {
    if (y & 1) a = a * b % mod;
    b = b * b % mod, y >>= 1;
  }
  return a;
}
void add(long long x, long long y, bool opt) {
  if (opt) {
    bool wtf = 0;
    long long nx = x, ny = y, posx = -1, posy = -1, asd = 1;
    while (1) {
      if (!wtf)
        nx += 1;
      else
        ny += 1;
      if (nx > n || ny > m) break;
      if (!zt[nx][ny]) {
        if (!wtf)
          posx = nx - 1, posy = ny;
        else
          posx = nx, posy = ny - 1;
        break;
      }
      asd += 1, wtf ^= 1;
    }
    wtf = 1;
    long long nx2 = x, ny2 = y, posx2 = -1, posy2 = -1, asd2 = 1;
    while (1) {
      if (!wtf)
        nx2 -= 1;
      else
        ny2 -= 1;
      if (nx2 < 1 || ny2 < 1) break;
      if (!zt[nx2][ny2]) {
        if (!wtf)
          posx2 = nx2 + 1, posy2 = ny2;
        else
          posx2 = nx2, posy2 = ny2 + 1;
        break;
      }
      asd2 += 1, wtf ^= 1;
    }
    ans += asd * asd2;
    wtf = 1;
    nx = x, ny = y, posx = -1, posy = -1, asd = 1;
    while (1) {
      if (!wtf)
        nx += 1;
      else
        ny += 1;
      if (nx > n || ny > m) break;
      if (!zt[nx][ny]) {
        if (!wtf)
          posx = nx - 1, posy = ny;
        else
          posx = nx, posy = ny - 1;
        break;
      }
      asd += 1, wtf ^= 1;
    }
    wtf = 0;
    nx2 = x, ny2 = y, posx2 = -1, posy2 = -1, asd2 = 1;
    while (1) {
      if (!wtf)
        nx2 -= 1;
      else
        ny2 -= 1;
      if (nx2 < 1 || ny2 < 1) break;
      if (!zt[nx2][ny2]) {
        if (!wtf)
          posx2 = nx2 + 1, posy2 = ny2;
        else
          posx2 = nx2, posy2 = ny2 + 1;
        break;
      }
      asd2 += 1, wtf ^= 1;
    }
    ans += asd * asd2, ans -= 1;
  } else {
    bool wtf = 0;
    long long nx = x, ny = y, posx = -1, posy = -1, asd = 1;
    while (1) {
      if (!wtf)
        nx += 1;
      else
        ny += 1;
      if (nx > n || ny > m) break;
      if (!zt[nx][ny]) {
        if (!wtf)
          posx = nx - 1, posy = ny;
        else
          posx = nx, posy = ny - 1;
        break;
      }
      asd += 1, wtf ^= 1;
    }
    wtf = 1;
    long long nx2 = x, ny2 = y, posx2 = -1, posy2 = -1, asd2 = 1;
    while (1) {
      if (!wtf)
        nx2 -= 1;
      else
        ny2 -= 1;
      if (nx2 < 1 || ny2 < 1) break;
      if (!zt[nx2][ny2]) {
        if (!wtf)
          posx2 = nx2 + 1, posy2 = ny2;
        else
          posx2 = nx2, posy2 = ny2 + 1;
        break;
      }
      asd2 += 1, wtf ^= 1;
    }
    ans -= asd * asd2;
    wtf = 1;
    nx = x, ny = y, posx = -1, posy = -1, asd = 1;
    while (1) {
      if (!wtf)
        nx += 1;
      else
        ny += 1;
      if (nx > n || ny > m) break;
      if (!zt[nx][ny]) {
        if (!wtf)
          posx = nx - 1, posy = ny;
        else
          posx = nx, posy = ny - 1;
        break;
      }
      asd += 1, wtf ^= 1;
    }
    wtf = 0;
    nx2 = x, ny2 = y, posx2 = -1, posy2 = -1, asd2 = 1;
    while (1) {
      if (!wtf)
        nx2 -= 1;
      else
        ny2 -= 1;
      if (nx2 < 1 || ny2 < 1) break;
      if (!zt[nx2][ny2]) {
        if (!wtf)
          posx2 = nx2 + 1, posy2 = ny2;
        else
          posx2 = nx2, posy2 = ny2 + 1;
        break;
      }
      asd2 += 1, wtf ^= 1;
    }
    ans -= asd * asd2, ans += 1;
  }
}
int main() {
  while (t--) {
    n = read(), m = read(), q = read();
    for (long long i = 1; i <= n; i += 1)
      for (long long j = 1; j <= m; j += 1) {
        zt[i][j] = 1;
        if (i == j)
          ans += 2 * (2 * i - 1) - 1;
        else if (i > j)
          ans += 2 * (2 * j - 1);
        else
          ans += 2 * (2 * i - 1);
      }
    while (q--) {
      x = read(), y = read();
      zt[x][y] ^= 1, add(x, y, zt[x][y]);
      printf("%lld\n", ans);
    }
  }
  return 0;
}

### Prompt

In CPP, your task is to solve the following problem:

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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
long long t = 1, n, m, k, q, l, r, ans, a[1009][1009], dy[1009][1009],
          xy[1009][1009], zt[1009][1009], b, c, u, v, x, y, z, mod = 1e9 + 7;
string s;
struct st {
  long long x, y;
};
bool cmp(const st &a, const st &b) { return a.x < b.x; }
inline long long read() {
  long long s = 0, w = 1;
  char ch = getchar();
  while (ch > '9' || ch < '0') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch <= '9' && ch >= '0')
    s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
  return s * w;
}
long long qp(long long x, long long y) {
  long long a = 1, b = x;
  while (y) {
    if (y & 1) a = a * b % mod;
    b = b * b % mod, y >>= 1;
  }
  return a;
}
void add(long long x, long long y, bool opt) {
  if (opt) {
    bool wtf = 0;
    long long nx = x, ny = y, posx = -1, posy = -1, asd = 1;
    while (1) {
      if (!wtf)
        nx += 1;
      else
        ny += 1;
      if (nx > n || ny > m) break;
      if (!zt[nx][ny]) {
        if (!wtf)
          posx = nx - 1, posy = ny;
        else
          posx = nx, posy = ny - 1;
        break;
      }
      asd += 1, wtf ^= 1;
    }
    wtf = 1;
    long long nx2 = x, ny2 = y, posx2 = -1, posy2 = -1, asd2 = 1;
    while (1) {
      if (!wtf)
        nx2 -= 1;
      else
        ny2 -= 1;
      if (nx2 < 1 || ny2 < 1) break;
      if (!zt[nx2][ny2]) {
        if (!wtf)
          posx2 = nx2 + 1, posy2 = ny2;
        else
          posx2 = nx2, posy2 = ny2 + 1;
        break;
      }
      asd2 += 1, wtf ^= 1;
    }
    ans += asd * asd2;
    wtf = 1;
    nx = x, ny = y, posx = -1, posy = -1, asd = 1;
    while (1) {
      if (!wtf)
        nx += 1;
      else
        ny += 1;
      if (nx > n || ny > m) break;
      if (!zt[nx][ny]) {
        if (!wtf)
          posx = nx - 1, posy = ny;
        else
          posx = nx, posy = ny - 1;
        break;
      }
      asd += 1, wtf ^= 1;
    }
    wtf = 0;
    nx2 = x, ny2 = y, posx2 = -1, posy2 = -1, asd2 = 1;
    while (1) {
      if (!wtf)
        nx2 -= 1;
      else
        ny2 -= 1;
      if (nx2 < 1 || ny2 < 1) break;
      if (!zt[nx2][ny2]) {
        if (!wtf)
          posx2 = nx2 + 1, posy2 = ny2;
        else
          posx2 = nx2, posy2 = ny2 + 1;
        break;
      }
      asd2 += 1, wtf ^= 1;
    }
    ans += asd * asd2, ans -= 1;
  } else {
    bool wtf = 0;
    long long nx = x, ny = y, posx = -1, posy = -1, asd = 1;
    while (1) {
      if (!wtf)
        nx += 1;
      else
        ny += 1;
      if (nx > n || ny > m) break;
      if (!zt[nx][ny]) {
        if (!wtf)
          posx = nx - 1, posy = ny;
        else
          posx = nx, posy = ny - 1;
        break;
      }
      asd += 1, wtf ^= 1;
    }
    wtf = 1;
    long long nx2 = x, ny2 = y, posx2 = -1, posy2 = -1, asd2 = 1;
    while (1) {
      if (!wtf)
        nx2 -= 1;
      else
        ny2 -= 1;
      if (nx2 < 1 || ny2 < 1) break;
      if (!zt[nx2][ny2]) {
        if (!wtf)
          posx2 = nx2 + 1, posy2 = ny2;
        else
          posx2 = nx2, posy2 = ny2 + 1;
        break;
      }
      asd2 += 1, wtf ^= 1;
    }
    ans -= asd * asd2;
    wtf = 1;
    nx = x, ny = y, posx = -1, posy = -1, asd = 1;
    while (1) {
      if (!wtf)
        nx += 1;
      else
        ny += 1;
      if (nx > n || ny > m) break;
      if (!zt[nx][ny]) {
        if (!wtf)
          posx = nx - 1, posy = ny;
        else
          posx = nx, posy = ny - 1;
        break;
      }
      asd += 1, wtf ^= 1;
    }
    wtf = 0;
    nx2 = x, ny2 = y, posx2 = -1, posy2 = -1, asd2 = 1;
    while (1) {
      if (!wtf)
        nx2 -= 1;
      else
        ny2 -= 1;
      if (nx2 < 1 || ny2 < 1) break;
      if (!zt[nx2][ny2]) {
        if (!wtf)
          posx2 = nx2 + 1, posy2 = ny2;
        else
          posx2 = nx2, posy2 = ny2 + 1;
        break;
      }
      asd2 += 1, wtf ^= 1;
    }
    ans -= asd * asd2, ans += 1;
  }
}
int main() {
  while (t--) {
    n = read(), m = read(), q = read();
    for (long long i = 1; i <= n; i += 1)
      for (long long j = 1; j <= m; j += 1) {
        zt[i][j] = 1;
        if (i == j)
          ans += 2 * (2 * i - 1) - 1;
        else if (i > j)
          ans += 2 * (2 * j - 1);
        else
          ans += 2 * (2 * i - 1);
      }
    while (q--) {
      x = read(), y = read();
      zt[x][y] ^= 1, add(x, y, zt[x][y]);
      printf("%lld\n", ans);
    }
  }
  return 0;
}

```