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: #! /usr/bin/env python
  #-*- coding: utf-8 -*-
   
  #####################################################
  # Copyright (c) 2021 Roee Xu. All Rights Reserved
  #####################################################
  # File:    E.py
  # Author:  root
  # Date:    2021-10-10 18:23:33
  # Brief:
  #####################################################
  
  import sys
  import collections
  import bisect
  
  def nc2(n):
      return n * (n - 1) // 2
  
  n, m, q = [int(x) for x in sys.stdin.readline().strip().split(' ')]
  board = collections.defaultdict(list)
  stand = {}
  visit = set()
  res = m * n
  for i in range(n + 1, 1, -1):
      # start with (i-1,1), down first
      g = min(n - i + 1, m - 1)
      # end point
      x, y = i - 1 + g, 1 + g 
      # if can be down more
      if x < n: 
          x += 1
      # away from start
      v = x - i + 1 + y - 1
      # value range list
      board[2 - i] = [-1, v + 1]
      # stair numbers
      res += nc2(v + 1)
      # start point
      stand[2 - i] = (i - 1, 1)
  for j in range(1, m + 1):
      # start with (1,j), right first
      g = min(n - 1, m - j)
      x, y = 1 + g, j + g
      if y < m:
          y += 1
      v = x - 1 + y - j
      board[j] = [-1, v + 1]
      res += nc2(v + 1)
      stand[j] = (1, j)
      
  # print(stand)
  # print(board)
  # print(res)
  
  def delta(idx, v):
      if v < 0:
          return 0
      p = bisect.bisect_left(board[idx], v)
      if v == board[idx][p]:
          # add
          l, r = board[idx][p - 1], board[idx][p + 1]
          board[idx].pop(p)
          return nc2(r - l - 1) - nc2(v - l - 1) - nc2(r - v - 1)
  
      else:
          # del
          bisect.insort_left(board[idx], v)
          assert v == board[idx][p]
          l, r = board[idx][p - 1], board[idx][p + 1]
          return - nc2(r - l - 1) + nc2(v - l - 1) + nc2(r - v - 1)
  
  for _ in range(q):
      a, b = [int(x) for x in sys.stdin.readline().strip().split(' ')]
      
      # first stair
      idx = b - a + 1
      v = b - stand[idx][1] + a - stand[idx][0]
      res += delta(idx, v)
  
      # second stair
      idx = b - a
      v = b - stand[idx][1] + a - stand[idx][0]
      res += delta(idx, v)
      
      # single stair
      if (a, b) in visit:
          res += 1
          visit.remove((a, b))
      else:
          res -= 1
          visit.add((a, b))
  
      # print res
      print(res)
          
  
  # vim: set expandtab ts=4 sw=4 sts=4 tw=100
  
  