description: 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
solution: import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.*;
  
  public class E {
      static int n,m,q;
      public static class RedBlackBST<Key extends Comparable<Key>, Value> {
  
          private static final boolean RED   = true;
          private static final boolean BLACK = false;
  
          private Node root;     // root of the BST
  
          // BST helper node data type
          private class Node {
              private Key key;           // key
              private Value val;         // associated data
              private Node left, right;  // links to left and right subtrees
              private boolean color;     // color of parent link
              private int size;          // subtree count
  
              public Node(Key key, Value val, boolean color, int size) {
                  this.key = key;
                  this.val = val;
                  this.color = color;
                  this.size = size;
              }
          }
  
          /**
           * Initializes an empty symbol table.
           */
          public RedBlackBST() {
          }
  
          /***************************************************************************
           *  Node helper methods.
           ***************************************************************************/
          // is node x red; false if x is null ?
          private boolean isRed(Node x) {
              if (x == null) return false;
              return x.color == RED;
          }
  
          // number of node in subtree rooted at x; 0 if x is null
          private int size(Node x) {
              if (x == null) return 0;
              return x.size;
          }
  
  
          /**
           * Returns the number of key-value pairs in this symbol table.
           * @return the number of key-value pairs in this symbol table
           */
          public int size() {
              return size(root);
          }
  
          /**
           * Is this symbol table empty?
           * @return {@code true} if this symbol table is empty and {@code false} otherwise
           */
          public boolean isEmpty() {
              return root == null;
          }
  
  
          /***************************************************************************
           *  Standard BST search.
           ***************************************************************************/
  
          /**
           * Returns the value associated with the given key.
           * @param key the key
           * @return the value associated with the given key if the key is in the symbol table
           *     and {@code null} if the key is not in the symbol table
           * @throws IllegalArgumentException if {@code key} is {@code null}
           */
          public Value get(Key key) {
              if (key == null) throw new IllegalArgumentException("argument to get() is null");
              return get(root, key);
          }
  
          // value associated with the given key in subtree rooted at x; null if no such key
          private Value get(Node x, Key key) {
              while (x != null) {
                  int cmp = key.compareTo(x.key);
                  if      (cmp < 0) x = x.left;
                  else if (cmp > 0) x = x.right;
                  else              return x.val;
              }
              return null;
          }
  
          /**
           * Does this symbol table contain the given key?
           * @param key the key
           * @return {@code true} if this symbol table contains {@code key} and
           *     {@code false} otherwise
           * @throws IllegalArgumentException if {@code key} is {@code null}
           */
          public boolean contains(Key key) {
              return get(key) != null;
          }
  
          /***************************************************************************
           *  Red-black tree insertion.
           ***************************************************************************/
  
          /**
           * Inserts the specified key-value pair into the symbol table, overwriting the old
           * value with the new value if the symbol table already contains the specified key.
           * Deletes the specified key (and its associated value) from this symbol table
           * if the specified value is {@code null}.
           *
           * @param key the key
           * @param val the value
           * @throws IllegalArgumentException if {@code key} is {@code null}
           */
          public void put(Key key, Value val) {
              if (key == null) throw new IllegalArgumentException("first argument to put() is null");
              if (val == null) {
                  delete(key);
                  return;
              }
  
              root = put(root, key, val);
              root.color = BLACK;
              // assert check();
          }
  
          // insert the key-value pair in the subtree rooted at h
          private Node put(Node h, Key key, Value val) {
              if (h == null) return new Node(key, val, RED, 1);
  
              int cmp = key.compareTo(h.key);
              if      (cmp < 0) h.left  = put(h.left,  key, val);
              else if (cmp > 0) h.right = put(h.right, key, val);
              else              h.val   = val;
  
              // fix-up any right-leaning links
              if (isRed(h.right) && !isRed(h.left))      h = rotateLeft(h);
              if (isRed(h.left)  &&  isRed(h.left.left)) h = rotateRight(h);
              if (isRed(h.left)  &&  isRed(h.right))     flipColors(h);
              h.size = size(h.left) + size(h.right) + 1;
  
              return h;
          }
  
          /***************************************************************************
           *  Red-black tree deletion.
           ***************************************************************************/
  
          /**
           * Removes the smallest key and associated value from the symbol table.
           * @throws NoSuchElementException if the symbol table is empty
           */
          public void deleteMin() {
              if (isEmpty()) throw new NoSuchElementException("BST underflow");
  
              // if both children of root are black, set root to red
              if (!isRed(root.left) && !isRed(root.right))
                  root.color = RED;
  
              root = deleteMin(root);
              if (!isEmpty()) root.color = BLACK;
              // assert check();
          }
  
          // delete the key-value pair with the minimum key rooted at h
          private Node deleteMin(Node h) {
              if (h.left == null)
                  return null;
  
              if (!isRed(h.left) && !isRed(h.left.left))
                  h = moveRedLeft(h);
  
              h.left = deleteMin(h.left);
              return balance(h);
          }
  
  
          /**
           * Removes the largest key and associated value from the symbol table.
           * @throws NoSuchElementException if the symbol table is empty
           */
          public void deleteMax() {
              if (isEmpty()) throw new NoSuchElementException("BST underflow");
  
              // if both children of root are black, set root to red
              if (!isRed(root.left) && !isRed(root.right))
                  root.color = RED;
  
              root = deleteMax(root);
              if (!isEmpty()) root.color = BLACK;
              // assert check();
          }
  
          // delete the key-value pair with the maximum key rooted at h
          private Node deleteMax(Node h) {
              if (isRed(h.left))
                  h = rotateRight(h);
  
              if (h.right == null)
                  return null;
  
              if (!isRed(h.right) && !isRed(h.right.left))
                  h = moveRedRight(h);
  
              h.right = deleteMax(h.right);
  
              return balance(h);
          }
  
          /**
           * Removes the specified key and its associated value from this symbol table
           * (if the key is in this symbol table).
           *
           * @param  key the key
           * @throws IllegalArgumentException if {@code key} is {@code null}
           */
          public void delete(Key key) {
              if (key == null) throw new IllegalArgumentException("argument to delete() is null");
              if (!contains(key)) return;
  
              // if both children of root are black, set root to red
              if (!isRed(root.left) && !isRed(root.right))
                  root.color = RED;
  
              root = delete(root, key);
              if (!isEmpty()) root.color = BLACK;
              // assert check();
          }
  
          // delete the key-value pair with the given key rooted at h
          private Node delete(Node h, Key key) {
              // assert get(h, key) != null;
  
              if (key.compareTo(h.key) < 0)  {
                  if (!isRed(h.left) && !isRed(h.left.left))
                      h = moveRedLeft(h);
                  h.left = delete(h.left, key);
              }
              else {
                  if (isRed(h.left))
                      h = rotateRight(h);
                  if (key.compareTo(h.key) == 0 && (h.right == null))
                      return null;
                  if (!isRed(h.right) && !isRed(h.right.left))
                      h = moveRedRight(h);
                  if (key.compareTo(h.key) == 0) {
                      Node x = min(h.right);
                      h.key = x.key;
                      h.val = x.val;
                      // h.val = get(h.right, min(h.right).key);
                      // h.key = min(h.right).key;
                      h.right = deleteMin(h.right);
                  }
                  else h.right = delete(h.right, key);
              }
              return balance(h);
          }
  
          /***************************************************************************
           *  Red-black tree helper functions.
           ***************************************************************************/
  
          // make a left-leaning link lean to the right
          private Node rotateRight(Node h) {
              assert (h != null) && isRed(h.left);
              // assert (h != null) && isRed(h.left) &&  !isRed(h.right);  // for insertion only
              Node x = h.left;
              h.left = x.right;
              x.right = h;
              x.color = x.right.color;
              x.right.color = RED;
              x.size = h.size;
              h.size = size(h.left) + size(h.right) + 1;
              return x;
          }
  
          // make a right-leaning link lean to the left
          private Node rotateLeft(Node h) {
              assert (h != null) && isRed(h.right);
              // assert (h != null) && isRed(h.right) && !isRed(h.left);  // for insertion only
              Node x = h.right;
              h.right = x.left;
              x.left = h;
              x.color = x.left.color;
              x.left.color = RED;
              x.size = h.size;
              h.size = size(h.left) + size(h.right) + 1;
              return x;
          }
  
          // flip the colors of a node and its two children
          private void flipColors(Node h) {
              // h must have opposite color of its two children
              // assert (h != null) && (h.left != null) && (h.right != null);
              // assert (!isRed(h) &&  isRed(h.left) &&  isRed(h.right))
              //    || (isRed(h)  && !isRed(h.left) && !isRed(h.right));
              h.color = !h.color;
              h.left.color = !h.left.color;
              h.right.color = !h.right.color;
          }
  
          // Assuming that h is red and both h.left and h.left.left
          // are black, make h.left or one of its children red.
          private Node moveRedLeft(Node h) {
              // assert (h != null);
              // assert isRed(h) && !isRed(h.left) && !isRed(h.left.left);
  
              flipColors(h);
              if (isRed(h.right.left)) {
                  h.right = rotateRight(h.right);
                  h = rotateLeft(h);
                  flipColors(h);
              }
              return h;
          }
  
          // Assuming that h is red and both h.right and h.right.left
          // are black, make h.right or one of its children red.
          private Node moveRedRight(Node h) {
              // assert (h != null);
              // assert isRed(h) && !isRed(h.right) && !isRed(h.right.left);
              flipColors(h);
              if (isRed(h.left.left)) {
                  h = rotateRight(h);
                  flipColors(h);
              }
              return h;
          }
  
          // restore red-black tree invariant
          private Node balance(Node h) {
              // assert (h != null);
  
              if (isRed(h.right) && !isRed(h.left))    h = rotateLeft(h);
              if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
              if (isRed(h.left) && isRed(h.right))     flipColors(h);
  
              h.size = size(h.left) + size(h.right) + 1;
              return h;
          }
  
  
          /***************************************************************************
           *  Utility functions.
           ***************************************************************************/
  
          /**
           * Returns the height of the BST (for debugging).
           * @return the height of the BST (a 1-node tree has height 0)
           */
          public int height() {
              return height(root);
          }
          private int height(Node x) {
              if (x == null) return -1;
              return 1 + Math.max(height(x.left), height(x.right));
          }
  
          /***************************************************************************
           *  Ordered symbol table methods.
           ***************************************************************************/
  
          /**
           * Returns the smallest key in the symbol table.
           * @return the smallest key in the symbol table
           * @throws NoSuchElementException if the symbol table is empty
           */
          public Key min() {
              if (isEmpty()) throw new NoSuchElementException("calls min() with empty symbol table");
              return min(root).key;
          }
  
          // the smallest key in subtree rooted at x; null if no such key
          private Node min(Node x) {
              // assert x != null;
              if (x.left == null) return x;
              else                return min(x.left);
          }
  
          /**
           * Returns the largest key in the symbol table.
           * @return the largest key in the symbol table
           * @throws NoSuchElementException if the symbol table is empty
           */
          public Key max() {
              if (isEmpty()) throw new NoSuchElementException("calls max() with empty symbol table");
              return max(root).key;
          }
  
          // the largest key in the subtree rooted at x; null if no such key
          private Node max(Node x) {
              // assert x != null;
              if (x.right == null) return x;
              else                 return max(x.right);
          }
  
  
          /**
           * Returns the largest key in the symbol table less than or equal to {@code key}.
           * @param key the key
           * @return the largest key in the symbol table less than or equal to {@code key}
           * @throws NoSuchElementException if there is no such key
           * @throws IllegalArgumentException if {@code key} is {@code null}
           */
          public Key floor(Key key) {
              if (key == null) throw new IllegalArgumentException("argument to floor() is null");
              if (isEmpty()) throw new NoSuchElementException("calls floor() with empty symbol table");
              Node x = floor(root, key);
              if (x == null) throw new NoSuchElementException("argument to floor() is too small");
              else           return x.key;
          }
  
          // the largest key in the subtree rooted at x less than or equal to the given key
          private Node floor(Node x, Key key) {
              if (x == null) return null;
              int cmp = key.compareTo(x.key);
              if (cmp == 0) return x;
              if (cmp < 0)  return floor(x.left, key);
              Node t = floor(x.right, key);
              if (t != null) return t;
              else           return x;
          }
  
          /**
           * Returns the smallest key in the symbol table greater than or equal to {@code key}.
           * @param key the key
           * @return the smallest key in the symbol table greater than or equal to {@code key}
           * @throws NoSuchElementException if there is no such key
           * @throws IllegalArgumentException if {@code key} is {@code null}
           */
          public Key ceiling(Key key) {
              if (key == null) throw new IllegalArgumentException("argument to ceiling() is null");
              if (isEmpty()) throw new NoSuchElementException("calls ceiling() with empty symbol table");
              Node x = ceiling(root, key);
              if (x == null) throw new NoSuchElementException("argument to ceiling() is too small");
              else           return x.key;
          }
  
          // the smallest key in the subtree rooted at x greater than or equal to the given key
          private Node ceiling(Node x, Key key) {
              if (x == null) return null;
              int cmp = key.compareTo(x.key);
              if (cmp == 0) return x;
              if (cmp > 0)  return ceiling(x.right, key);
              Node t = ceiling(x.left, key);
              if (t != null) return t;
              else           return x;
          }
  
          /**
           * Return the key in the symbol table of a given {@code rank}.
           * This key has the property that there are {@code rank} keys in
           * the symbol table that are smaller. In other words, this key is the
           * ({@code rank}+1)st smallest key in the symbol table.
           *
           * @param  rank the order statistic
           * @return the key in the symbol table of given {@code rank}
           * @throws IllegalArgumentException unless {@code rank} is between 0 and
           *        <em>n</em>–1
           */
          public Key select(int rank) {
              if (rank < 0 || rank >= size()) {
                  throw new IllegalArgumentException("argument to select() is invalid: " + rank);
              }
              return select(root, rank);
          }
  
          // Return key in BST rooted at x of given rank.
          // Precondition: rank is in legal range.
          private Key select(Node x, int rank) {
              if (x == null) return null;
              int leftSize = size(x.left);
              if      (leftSize > rank) return select(x.left,  rank);
              else if (leftSize < rank) return select(x.right, rank - leftSize - 1);
              else                      return x.key;
          }
  
          /**
           * Return the number of keys in the symbol table strictly less than {@code key}.
           * @param key the key
           * @return the number of keys in the symbol table strictly less than {@code key}
           * @throws IllegalArgumentException if {@code key} is {@code null}
           */
          public int rank(Key key) {
              if (key == null) throw new IllegalArgumentException("argument to rank() is null");
              return rank(key, root);
          }
  
          // number of keys less than key in the subtree rooted at x
          private int rank(Key key, Node x) {
              if (x == null) return 0;
              int cmp = key.compareTo(x.key);
              if      (cmp < 0) return rank(key, x.left);
              else if (cmp > 0) return 1 + size(x.left) + rank(key, x.right);
              else              return size(x.left);
          }
  
          /***************************************************************************
           *  Range count and range search.
           ***************************************************************************/
  
          /**
           * Returns all keys in the symbol table as an {@code Iterable}.
           * To iterate over all of the keys in the symbol table named {@code st},
           * use the foreach notation: {@code for (Key key : st.keys())}.
           * @return all keys in the symbol table as an {@code Iterable}
           */
          public Iterable<Key> keys() {
              if (isEmpty()) return new LinkedList<>();
              return keys(min(), max());
          }
  
          /**
           * Returns all keys in the symbol table in the given range,
           * as an {@code Iterable}.
           *
           * @param  lo minimum endpoint
           * @param  hi maximum endpoint
           * @return all keys in the symbol table between {@code lo}
           *    (inclusive) and {@code hi} (inclusive) as an {@code Iterable}
           * @throws IllegalArgumentException if either {@code lo} or {@code hi}
           *    is {@code null}
           */
          public Iterable<Key> keys(Key lo, Key hi) {
              if (lo == null) throw new IllegalArgumentException("first argument to keys() is null");
              if (hi == null) throw new IllegalArgumentException("second argument to keys() is null");
  
              Queue<Key> queue = new LinkedList<Key>();
              // if (isEmpty() || lo.compareTo(hi) > 0) return queue;
              keys(root, queue, lo, hi);
              return queue;
          }
  
          // add the keys between lo and hi in the subtree rooted at x
          // to the queue
          private void keys(Node x, Queue<Key> queue, Key lo, Key hi) {
              if (x == null) return;
              int cmplo = lo.compareTo(x.key);
              int cmphi = hi.compareTo(x.key);
              if (cmplo < 0) keys(x.left, queue, lo, hi);
              if (cmplo <= 0 && cmphi >= 0) queue.add(x.key);
              if (cmphi > 0) keys(x.right, queue, lo, hi);
          }
  
          /**
           * Returns the number of keys in the symbol table in the given range.
           *
           * @param  lo minimum endpoint
           * @param  hi maximum endpoint
           * @return the number of keys in the symbol table between {@code lo}
           *    (inclusive) and {@code hi} (inclusive)
           * @throws IllegalArgumentException if either {@code lo} or {@code hi}
           *    is {@code null}
           */
          public int size(Key lo, Key hi) {
              if (lo == null) throw new IllegalArgumentException("first argument to size() is null");
              if (hi == null) throw new IllegalArgumentException("second argument to size() is null");
  
              if (lo.compareTo(hi) > 0) return 0;
              if (contains(hi)) return rank(hi) - rank(lo) + 1;
              else              return rank(hi) - rank(lo);
          }
  
  
          /***************************************************************************
           *  Check integrity of red-black tree data structure.
           ***************************************************************************/
          /*private boolean check() {
              if (!isBST())            StdOut.println("Not in symmetric order");
              if (!isSizeConsistent()) StdOut.println("Subtree counts not consistent");
              if (!isRankConsistent()) StdOut.println("Ranks not consistent");
              if (!is23())             StdOut.println("Not a 2-3 tree");
              if (!isBalanced())       StdOut.println("Not balanced");
              return isBST() && isSizeConsistent() && isRankConsistent() && is23() && isBalanced();
          }*/
  
          // does this binary tree satisfy symmetric order?
          // Note: this test also ensures that data structure is a binary tree since order is strict
          private boolean isBST() {
              return isBST(root, null, null);
          }
  
          // is the tree rooted at x a BST with all keys strictly between min and max
          // (if min or max is null, treat as empty constraint)
          // Credit: Bob Dondero's elegant solution
          private boolean isBST(Node x, Key min, Key max) {
              if (x == null) return true;
              if (min != null && x.key.compareTo(min) <= 0) return false;
              if (max != null && x.key.compareTo(max) >= 0) return false;
              return isBST(x.left, min, x.key) && isBST(x.right, x.key, max);
          }
  
          // are the size fields correct?
          private boolean isSizeConsistent() { return isSizeConsistent(root); }
          private boolean isSizeConsistent(Node x) {
              if (x == null) return true;
              if (x.size != size(x.left) + size(x.right) + 1) return false;
              return isSizeConsistent(x.left) && isSizeConsistent(x.right);
          }
  
          // check that ranks are consistent
          private boolean isRankConsistent() {
              for (int i = 0; i < size(); i++)
                  if (i != rank(select(i))) return false;
              for (Key key : keys())
                  if (key.compareTo(select(rank(key))) != 0) return false;
              return true;
          }
  
          // Does the tree have no red right links, and at most one (left)
          // red links in a row on any path?
          private boolean is23() { return is23(root); }
          private boolean is23(Node x) {
              if (x == null) return true;
              if (isRed(x.right)) return false;
              if (x != root && isRed(x) && isRed(x.left))
                  return false;
              return is23(x.left) && is23(x.right);
          }
  
          // do all paths from root to leaf have same number of black edges?
          private boolean isBalanced() {
              int black = 0;     // number of black links on path from root to min
              Node x = root;
              while (x != null) {
                  if (!isRed(x)) black++;
                  x = x.left;
              }
              return isBalanced(root, black);
          }
  
          // does every path from the root to a leaf have the given number of black links?
          private boolean isBalanced(Node x, int black) {
              if (x == null) return black == 0;
              if (!isRed(x)) black--;
              return isBalanced(x.left, black) && isBalanced(x.right, black);
          }
  
  
          /**
           * Unit tests the {@code RedBlackBST} data type.
           *
           * @param args the command-line arguments
           */
          /*public static void main(String[] args) {
              RedBlackBST<String, Integer> st = new RedBlackBST<String, Integer>();
              for (int i = 0; !StdIn.isEmpty(); i++) {
                  String key = StdIn.readString();
                  st.put(key, i);
              }
              StdOut.println();
              for (String s : st.keys())
                  StdOut.println(s + " " + st.get(s));
              StdOut.println();
          }*/
      }
      static class Cell implements Comparable<Cell> {
          int x,y;
  
          public Cell(int x, int y) {
              this.x=x;this.y=y;
          }
          public int distTo(Cell o) {
              return Math.abs(this.x + this.y - (o.x + o.y));
          }
          @Override
          public int compareTo(Cell o) {
              if (this.x + this.y != o.x + o.y) {
                  return this.x + this.y - (o.x + o.y);
              }
              return this.x - o.x;
          }
          @Override
          public int hashCode() {
              return x*n+y;
          }
          @Override
          public boolean equals(Object o) {
              if (!(o instanceof  Cell)) return false;
              Cell c=(Cell) o;
              return c.x==x && c.y==y;
          }
      }
      static class Stair {
          int startx, starty;
          boolean startRight;
          int len;
          RedBlackBST<Cell, Integer> blocked = new RedBlackBST<>();
          public Stair(int x, int y, boolean right) {
              startx=x; starty=y; startRight=right;
              len = allCells().size();
          }
          public ArrayList<Cell> allCells() {
              ArrayList<Cell> l=new ArrayList<>();
              int x=startx, y=starty;
              boolean right=startRight;
              while (x>=0 && x<n && y>=0 && y<m) {
                  l.add(new Cell(x,y));
                  if (right) {y++;} else {x++;}
                  right = !right;
              }
              return l;
          }
          public long initCount() {
              return (long) len*(len+1)/2 - len;
          }
          public int pos(Cell c) {  // index of cell in staircase
              return c.x+c.y-startx-starty;
          }
          public int pos(int x, int y) {return pos(new Cell(x,y));}
          public long block(Cell c) {
              if (blocked.contains(c)) return 0;
              long change = 0;
              long before=0, after=0;  // free spaces before and after c
              Cell prev, next;
              try {
                  prev = blocked.floor(c);
              } catch (NoSuchElementException e) {
                  prev = null;
              }
              try {
                  next = blocked.ceiling(c);
              } catch (NoSuchElementException e) {
                  next = null;
              }
              before = (prev==null)? pos(c): c.distTo(prev)-1;
              after = (next==null)? len-pos(c)-1: c.distTo(next)-1;
              change -= before * (after+1) + after * (before+1) - before*after;// + 1;
  
              blocked.put(c, 1);
              //System.out.println("Block " + this.startx + this.starty + this.startRight + " " + c.x + c.y);
              //System.out.println(before+" "+after+" "+change);
              return change;
          }
          public long block(int x, int y) {return block(new Cell(x,y));}
  
          public long free(Cell c) {
              if (!blocked.contains(c)) return 0;
              long change = 0;
              long before=0, after=0;  // free spaces before and after c
              Cell prev, next;
              blocked.delete(c);
  
              try {
                  prev = blocked.floor(c);
              } catch (NoSuchElementException e) {
                  prev = null;
              }
              try {
                  next = blocked.ceiling(c);
              } catch (NoSuchElementException e) {
                  next = null;
              }
              before = (prev==null)? pos(c): c.distTo(prev)-1;
              after = (next==null)? len-pos(c)-1: c.distTo(next)-1;
              change += before * (after+1) + after * (before+1)-before*after;// + 1;
              //System.out.println("Free " + this.startx + this.starty + this.startRight + " " + c.x + c.y);
              //System.out.println(before+" "+after+" "+change);
              return change;
          }
          public long free(int x, int y) {return free(new Cell(x,y));}
      }
  
      static boolean[][] blocked;
      static ArrayList<Stair> stairs=new ArrayList<>();
      static HashMap<Cell, ArrayList<Stair>> passthu = new HashMap<>();
      public static void main(String[] args) throws IOException {
          BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
          String[] str=in.readLine().split(" ");
          n=Integer.parseInt(str[0]);
          m=Integer.parseInt(str[1]);
          q=Integer.parseInt(str[2]);
  
          blocked = new boolean[n][m];
          long sum = 0;
          for (int j=0; j<m-1; j++) {
              Stair st = new Stair(0, j, true);
              stairs.add(st);
              for (Cell c : st.allCells()) {
                  passthu.putIfAbsent(c, new ArrayList<>());
                  passthu.get(c).add(st);
              }
              sum += st.initCount();
              //System.out.println(st.startx + " " + st.starty + " " + st.startRight + " " + st.initCount());
          }
          for (int i=0; i<n-1; i++) {
              Stair st = new Stair(i, 0, false);
              stairs.add(st);
              for (Cell c : st.allCells()) {
                  passthu.putIfAbsent(c, new ArrayList<>());
                  passthu.get(c).add(st);
              }
              sum += st.initCount();
              //System.out.println(st.startx + " " + st.starty + " " + st.startRight + " " + st.initCount());
          }
          sum += n*m;  // All size-1 stairs are counted 0 times
          //System.out.println(sum);
  
          for (int i=0;i<q;i++) {
              str=in.readLine().split(" ");
              int x=Integer.parseInt(str[0])-1;
              int y=Integer.parseInt(str[1])-1;
              Cell c=new Cell(x,y);
              //System.out.println(passthu.containsKey(c));
              for (Stair st : passthu.getOrDefault(c, new ArrayList<>())) {
                  if (blocked[x][y]) {
                      // free
                      sum += st.free(c);
                  } else {
                      // block
                      sum += st.block(c);
                      //System.out.println("S="+sum);
                  }
              }
              if (blocked[x][y]) {
                  sum += 1;  // size 1
                  blocked[x][y]=false;
              } else {
                  sum -= 1;  // size 1
                  blocked[x][y]=true;
              }
              System.out.println(sum);
          }
      }
  }
  