#include <bits/stdc++.h>
using namespace std;
long long denom = 1e9 + 7;
long long powmod(long long a, long long b) {
  long long res = 1;
  a %= denom;
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % denom;
    a = a * a % denom;
  }
  return res;
}
int main(int argc, const char* argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long t = 1;
  while (t-- > 0) {
    long long n, m, q;
    cin >> n >> m >> q;
    vector<vector<bool>> isBlocked(n, vector<bool>(m, false));
    vector<pair<long long, long long>> move = {{0, 1}, {1, 0}};
    vector<vector<pair<long long, long long>>> hor;
    unordered_map<long long,
                  unordered_map<long long, vector<pair<long long, long long>>>>
        horIdx;
    for (long long j = (0); j < (m - 1); j++) {
      long long x = 0, y = j, k = 0;
      long long firstIndex = hor.size();
      vector<pair<long long, long long>> path;
      while (x < n && y < m) {
        horIdx[x][y].push_back({firstIndex, path.size()});
        path.push_back({x, y});
        x += move[k].first;
        y += move[k].second;
        k = (k + 1) % 2;
      }
      hor.push_back(path);
    }
    vector<set<long long>> horBlocked(hor.size());
    vector<vector<pair<long long, long long>>> ver;
    unordered_map<long long,
                  unordered_map<long long, vector<pair<long long, long long>>>>
        verIdx;
    for (long long i = (0); i < (n - 1); i++) {
      long long x = i, y = 0, k = 1;
      long long firstIndex = ver.size();
      vector<pair<long long, long long>> path;
      while (x < n && y < m) {
        verIdx[x][y].push_back({firstIndex, path.size()});
        path.push_back({x, y});
        x += move[k].first;
        y += move[k].second;
        k = (k + 1) % 2;
      }
      ver.push_back(path);
    }
    vector<set<long long>> verBlocked(ver.size());
    long long total = 0;
    for (auto& a : hor) {
      long long c = a.size();
      total += c * (c + 1) / 2;
    }
    for (auto& a : ver) {
      long long c = a.size();
      total += c * (c + 1) / 2;
    }
    for (long long i = (0); i < (n); i++)
      for (long long j = (0); j < (m); j++)
        total -= ((long long)horIdx[i][j].size() +
                  (long long)verIdx[i][j].size() - 1);
    long long curr = total;
    for (long long i = (0); i < (q); i++) {
      long long a, b;
      cin >> a >> b;
      a--;
      b--;
      long long d = 0;
      for (auto p : horIdx[a][b]) {
        long long l = -1, h = hor[p.first].size();
        set<long long>& s_block = horBlocked[p.first];
        if (isBlocked[a][b]) s_block.erase(p.second);
        auto it1 = s_block.lower_bound(p.second);
        if (it1 != s_block.end()) {
          h = *it1;
        }
        if (it1 != s_block.begin()) {
          it1--;
          l = *it1;
        }
        d += (p.second - l) * (h - p.second);
        if (!isBlocked[a][b]) s_block.insert(p.second);
      }
      for (auto p : verIdx[a][b]) {
        long long l = -1, h = ver[p.first].size();
        set<long long>& s_block = verBlocked[p.first];
        if (isBlocked[a][b]) s_block.erase(p.second);
        auto it1 = s_block.lower_bound(p.second);
        if (it1 != s_block.end()) {
          h = *it1;
        }
        if (it1 != s_block.begin()) {
          it1--;
          l = *it1;
        }
        d += (p.second - l) * (h - p.second);
        if (!isBlocked[a][b]) s_block.insert(p.second);
      }
      if (isBlocked[a][b]) {
        curr += d;
        curr -= ((long long)horIdx[a][b].size() +
                 (long long)verIdx[a][b].size() - 1);
      } else {
        curr -= d;
        curr += ((long long)horIdx[a][b].size() +
                 (long long)verIdx[a][b].size() - 1);
      }
      isBlocked[a][b] = !isBlocked[a][b];
      cout << curr << endl;
    }
  }
  return 0;
}

### Prompt

Create a solution in Cpp for 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 denom = 1e9 + 7;
long long powmod(long long a, long long b) {
  long long res = 1;
  a %= denom;
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % denom;
    a = a * a % denom;
  }
  return res;
}
int main(int argc, const char* argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long t = 1;
  while (t-- > 0) {
    long long n, m, q;
    cin >> n >> m >> q;
    vector<vector<bool>> isBlocked(n, vector<bool>(m, false));
    vector<pair<long long, long long>> move = {{0, 1}, {1, 0}};
    vector<vector<pair<long long, long long>>> hor;
    unordered_map<long long,
                  unordered_map<long long, vector<pair<long long, long long>>>>
        horIdx;
    for (long long j = (0); j < (m - 1); j++) {
      long long x = 0, y = j, k = 0;
      long long firstIndex = hor.size();
      vector<pair<long long, long long>> path;
      while (x < n && y < m) {
        horIdx[x][y].push_back({firstIndex, path.size()});
        path.push_back({x, y});
        x += move[k].first;
        y += move[k].second;
        k = (k + 1) % 2;
      }
      hor.push_back(path);
    }
    vector<set<long long>> horBlocked(hor.size());
    vector<vector<pair<long long, long long>>> ver;
    unordered_map<long long,
                  unordered_map<long long, vector<pair<long long, long long>>>>
        verIdx;
    for (long long i = (0); i < (n - 1); i++) {
      long long x = i, y = 0, k = 1;
      long long firstIndex = ver.size();
      vector<pair<long long, long long>> path;
      while (x < n && y < m) {
        verIdx[x][y].push_back({firstIndex, path.size()});
        path.push_back({x, y});
        x += move[k].first;
        y += move[k].second;
        k = (k + 1) % 2;
      }
      ver.push_back(path);
    }
    vector<set<long long>> verBlocked(ver.size());
    long long total = 0;
    for (auto& a : hor) {
      long long c = a.size();
      total += c * (c + 1) / 2;
    }
    for (auto& a : ver) {
      long long c = a.size();
      total += c * (c + 1) / 2;
    }
    for (long long i = (0); i < (n); i++)
      for (long long j = (0); j < (m); j++)
        total -= ((long long)horIdx[i][j].size() +
                  (long long)verIdx[i][j].size() - 1);
    long long curr = total;
    for (long long i = (0); i < (q); i++) {
      long long a, b;
      cin >> a >> b;
      a--;
      b--;
      long long d = 0;
      for (auto p : horIdx[a][b]) {
        long long l = -1, h = hor[p.first].size();
        set<long long>& s_block = horBlocked[p.first];
        if (isBlocked[a][b]) s_block.erase(p.second);
        auto it1 = s_block.lower_bound(p.second);
        if (it1 != s_block.end()) {
          h = *it1;
        }
        if (it1 != s_block.begin()) {
          it1--;
          l = *it1;
        }
        d += (p.second - l) * (h - p.second);
        if (!isBlocked[a][b]) s_block.insert(p.second);
      }
      for (auto p : verIdx[a][b]) {
        long long l = -1, h = ver[p.first].size();
        set<long long>& s_block = verBlocked[p.first];
        if (isBlocked[a][b]) s_block.erase(p.second);
        auto it1 = s_block.lower_bound(p.second);
        if (it1 != s_block.end()) {
          h = *it1;
        }
        if (it1 != s_block.begin()) {
          it1--;
          l = *it1;
        }
        d += (p.second - l) * (h - p.second);
        if (!isBlocked[a][b]) s_block.insert(p.second);
      }
      if (isBlocked[a][b]) {
        curr += d;
        curr -= ((long long)horIdx[a][b].size() +
                 (long long)verIdx[a][b].size() - 1);
      } else {
        curr -= d;
        curr += ((long long)horIdx[a][b].size() +
                 (long long)verIdx[a][b].size() - 1);
      }
      isBlocked[a][b] = !isBlocked[a][b];
      cout << curr << endl;
    }
  }
  return 0;
}

```