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

Difficulty: HARD
Tags: Graph traversal

Combinatorics

Implementation

Complete search

Dynamic programming

Mathematics

Data structures
Skill types: Dynamic programming

Data structures

Complete search

Starter code:

Solutions:
import sys
input = sys.stdin.readline
output = sys.stdout.write

def solve(R, C, Q, queries):
	blocked = [[0] * C for _ in range(R)]
	res = R * C
	for c in range(C):
		for ln in range(1, R + C + 1):
			nr = ln // 2
			nc = c + (ln + 1) // 2
			if nr >= R or nc >= C:
				break
			res += ln
	for r in range(R):
		for ln in range(1, R + C + 1):
			nr = r + (ln + 1) // 2
			nc = ln // 2
			if nr >= R or nc >= C:
				break
			res += ln
	for (qr, qc) in queries:
		change = 1
		(r, c) = (qr, qc)
		up = down = 0
		for ln in range(1, R + C + 1):
			nr = r + ln // 2
			nc = c + (ln + 1) // 2
			if nr >= R or nc >= C or blocked[nr][nc]:
				break
			down += 1
		for ln in range(1, R + C + 1):
			nr = r - (ln + 1) // 2
			nc = c - ln // 2
			if nr < 0 or nc < 0 or blocked[nr][nc]:
				break
			up += 1
		change += up + down + up * down
		(r, c) = (qr, qc)
		up = down = 0
		for ln in range(1, R + C + 1):
			nr = r + (ln + 1) // 2
			nc = c + ln // 2
			if nr >= R or nc >= C or blocked[nr][nc]:
				break
			down += 1
		for ln in range(1, R + C + 1):
			nr = r - ln // 2
			nc = c - (ln + 1) // 2
			if nr < 0 or nc < 0 or blocked[nr][nc]:
				break
			up += 1
		change += up + down + up * down
		res += change if blocked[qr][qc] else -change
		blocked[qr][qc] ^= 1
		output(str(res) + '\n')

def main():
	(N, M, Q) = list(map(int, input().split()))
	queries = []
	for _ in range(Q):
		(x, y) = list(map(int, input().split()))
		queries.append((x - 1, y - 1))
	solve(N, M, Q, queries)
main()


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):
	g = min(n - i + 1, m - 1)
	(x, y) = (i - 1 + g, 1 + g)
	if x < n:
		x += 1
	v = x - i + 1 + y - 1
	board[2 - i] = [-1, v + 1]
	res += nc2(v + 1)
	stand[2 - i] = (i - 1, 1)
for j in range(1, m + 1):
	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)

def delta(idx, v):
	if v < 0:
		return 0
	p = bisect.bisect_left(board[idx], v)
	if v == board[idx][p]:
		(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:
		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(' ')]
	idx = b - a + 1
	v = b - stand[idx][1] + a - stand[idx][0]
	res += delta(idx, v)
	idx = b - a
	v = b - stand[idx][1] + a - stand[idx][0]
	res += delta(idx, v)
	if (a, b) in visit:
		res += 1
		visit.remove((a, b))
	else:
		res -= 1
		visit.add((a, b))
	print(res)


import sys
from sys import stdin

def calc(l):
	assert l >= 0
	return l * (l - 1) // 2
(n, m, q) = map(int, stdin.readline().split())
xy = []
color = [[0] * m for i in range(n)]
freenum = n * m
ans = 0
maxi = [float('-inf')] * 2002
mini = [float('inf')] * 2002
for i in range(n):
	for j in range(m):
		diff = i - j
		s = i + j
		maxi[diff] = max(maxi[diff], s)
		mini[diff] = min(mini[diff], s)
		diff = i - 1 - j
		s = i + j
		maxi[diff] = max(maxi[diff], s)
		mini[diff] = min(mini[diff], s)
ans = 0
for i in range(2002):
	if maxi[i] != float('-inf'):
		ans += calc(maxi[i] - mini[i] + 1)
ANS = []
for i in range(q):
	(x, y) = map(int, stdin.readline().split())
	x -= 1
	y -= 1
	xx = x
	yy = y - 1
	cnt = 0
	while xx >= 0 and yy >= 0 and (color[xx][yy] == 0):
		if cnt == 0:
			xx -= 1
		else:
			yy -= 1
		cnt ^= 1
	XX = x + 1
	YY = y
	cnt = 0
	while XX < n and YY < m and (color[XX][YY] == 0):
		if cnt == 0:
			YY += 1
		else:
			XX += 1
		cnt ^= 1
	sp = xx + yy
	sq = XX + YY
	sa = x + y
	if color[x][y] == 0:
		ans -= calc(sq - sp - 1)
		ans += calc(sa - sp - 1) + calc(sq - sa - 1)
	else:
		ans += calc(sq - sp - 1)
		ans -= calc(sa - sp - 1) + calc(sq - sa - 1)
	xx = x - 1
	yy = y
	cnt = 0
	while xx >= 0 and yy >= 0 and (color[xx][yy] == 0):
		if cnt == 0:
			yy -= 1
		else:
			xx -= 1
		cnt ^= 1
	XX = x
	YY = y + 1
	cnt = 0
	while XX < n and YY < m and (color[XX][YY] == 0):
		if cnt == 0:
			XX += 1
		else:
			YY += 1
		cnt ^= 1
	sp = xx + yy
	sq = XX + YY
	sa = x + y
	if color[x][y] == 0:
		ans -= calc(sq - sp - 1)
		ans += calc(sa - sp - 1) + calc(sq - sa - 1)
	else:
		ans += calc(sq - sp - 1)
		ans -= calc(sa - sp - 1) + calc(sq - sa - 1)
	if color[x][y] == 0:
		freenum -= 1
		color[x][y] = 1
	else:
		freenum += 1
		color[x][y] = 0
	ANS.append(ans + freenum)
print('\n'.join(map(str, ANS)))


def main():
	(H, W, Q) = map(int, input().split())
	A = [[] for _ in range(H + W)]
	for i in range(H):
		for j in range(W):
			A[(i + j + 1) // 2 * 2].append(0)
			A[(i + j) // 2 * 2 + 1].append(0)
	RawAns = H * W
	Diff = [0] * (H + W)
	for i in range(H + W):
		K = len(A[i]) * (len(A[i]) - 1) // 2
		Diff[i] = K
		RawAns += K
	for _ in range(Q):
		(h, w) = map(int, input().split())
		h -= 1
		w = W - w
		i1 = (h + w + 1) // 2 * 2
		j1 = h * 2 + (h + w) % 2 if i1 < W else (W - w - 1) * 2 + (h + w + 1) % 2
		i2 = (h + w) // 2 * 2 + 1
		j2 = h * 2 + (h + w + 1) % 2 if i2 < W else (W - w - 1) * 2 + (h + w) % 2
		if A[i1][j1]:
			RawAns += 1
		else:
			RawAns -= 1
		A[i1][j1] ^= 1
		A[i2][j2] ^= 1
		Tmp1 = 0
		Count = -1
		for a in A[i1]:
			if a:
				Tmp1 += Count * (Count + 1) // 2
				Count = -1
			else:
				Count += 1
		Tmp1 += Count * (Count + 1) // 2
		Tmp2 = 0
		Count = -1
		for a in A[i2]:
			if a:
				Tmp2 += Count * (Count + 1) // 2
				Count = -1
			else:
				Count += 1
		Tmp2 += Count * (Count + 1) // 2
		RawAns -= Diff[i1] - Tmp1 + Diff[i2] - Tmp2
		Diff[i1] = Tmp1
		Diff[i2] = Tmp2
		print(RawAns)
main()


from sys import stdin, stdout
input = stdin.readline
print = stdout.write
(n, m, q) = list(map(int, input().split()))
matrix = [[[0, 0] for i in range(m)] for j in range(n)]
free = [[True for i in range(m)] for j in range(n)]
ans = 0
for i in range(n):
	for j in range(m):
		if i > 0:
			matrix[i][j][1] += matrix[i - 1][j][0]
		if j > 0:
			matrix[i][j][0] += matrix[i][j - 1][1]
		matrix[i][j][0] += 1
		matrix[i][j][1] += 1
		ans += matrix[i][j][0] + matrix[i][j][1] - 1
for _ in range(q):
	(x, y) = list(map(int, input().split()))
	x -= 1
	y -= 1
	count_right = 0
	act_x = x
	act_y = y + 1
	right = True
	while act_x < n and act_y < m and free[act_x][act_y]:
		count_right += 1
		if right:
			act_x += 1
		else:
			act_y += 1
		right = not right
	count_down = 0
	act_x = x + 1
	act_y = y
	right = False
	while act_x < n and act_y < m and free[act_x][act_y]:
		count_down += 1
		if right:
			act_x += 1
		else:
			act_y += 1
		right = not right
	count_left = 0
	act_x = x
	act_y = y - 1
	left = True
	while act_x >= 0 and act_y >= 0 and free[act_x][act_y]:
		count_left += 1
		if left:
			act_x -= 1
		else:
			act_y -= 1
		left = not left
	count_up = 0
	act_x = x - 1
	act_y = y
	left = False
	while act_x >= 0 and act_y >= 0 and free[act_x][act_y]:
		count_up += 1
		if left:
			act_x -= 1
		else:
			act_y -= 1
		left = not left
	count_stairs = 0
	count_stairs += (count_up + 1) * (count_right + 1)
	count_stairs += (count_down + 1) * (count_left + 1)
	count_stairs -= 1
	if free[x][y]:
		ans -= count_stairs
	else:
		ans += count_stairs
	free[x][y] = not free[x][y]
	print(str(ans) + '\n')


class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

def solve():
	(n, m, q) = map(int, input().split())
	res = [[0 for j in range(m)] for i in range(n)]
	dp1 = [[0 for j in range(m)] for i in range(n)]
	dp2 = [[0 for j in range(m)] for i in range(n)]
	for i in range(n - 1):
		dp1[i][m - 1] = 1
	for j in range(m - 1):
		dp2[n - 1][j] = 1
	for i in range(n - 2, -1, -1):
		for j in range(m - 2, -1, -1):
			dp1[i][j] = dp2[i + 1][j] + 1
			dp2[i][j] = dp1[i][j + 1] + 1
	ans = sum((sum(a) for a in dp1)) + sum((sum(a) for a in dp2)) + m * n
	unblocked = [[1 for j in range(m)] for i in range(n)]
	L = [SortedList() for i in range(m + n + 3)]
	for i in range(-1, n):
		L[-i + n].add(i)
		L[m - i + n + 1].add(i)
	for j in range(m):
		L[j + 2 + n].add(-1)
		L[j + 1].add(n)
	L[m + 1].add(n)
	for _ in range(q):
		(x, y) = map(int, input().split())
		x -= 1
		y -= 1
		if unblocked[x][y] == 0:
			L[y - x + n + 1].remove(x)
		i1 = L[y - x + n + 1].bisect_left(x)
		x1 = L[y - x + n + 1][i1]
		x2 = L[y - x + n + 1][i1 - 1]
		i2 = L[y - x + n + 2].bisect_left(x)
		y1 = L[y - x + n + 2][i2]
		y2 = L[y - x + n + 2][i2 - 1]
		if x1 <= y1:
			c1 = 2 * (x1 - x)
		else:
			c1 = 2 * (y1 - x) + 1
		if x2 <= y2:
			c1 *= 2 * (x - y2) - 1
		else:
			c1 *= 2 * (x - x2)
		i2 = L[y - x + n].bisect_left(x + 1)
		y1 = L[y - x + n][i2]
		y2 = L[y - x + n][i2 - 1]
		if y1 <= x1:
			c2 = 2 * (y1 - x) - 1
		else:
			c2 = 2 * (x1 - x)
		if y2 <= x2:
			c2 *= 2 * (x - x2)
		else:
			c2 *= 2 * (x - y2) + 1
		if unblocked[x][y]:
			ans -= c1 + c2 - 1
			L[y - x + n + 1].add(x)
		else:
			ans += c1 + c2 - 1
		unblocked[x][y] = 1 - unblocked[x][y]
		print(ans)
import sys
input = lambda : sys.stdin.readline().rstrip()
solve()


class Array2d:

	def __init__(self, n, m, arr):
		self.n = n
		self.m = m
		self.arr = arr

	@classmethod
	def full(cls, n, m, fill_value):
		return cls(n, m, [fill_value] * (n * m))

	@classmethod
	def from_list(cls, lst):
		(n, m) = (len(lst), len(lst[0]))
		arr = [lst[0]] * (n * m)
		k = 0
		for row in lst:
			for v in row:
				arr[k] = v
				k += 1
		return cls(n, m, arr)

	def _get_view(self, i, j):
		i = tuple(range(0, self.n * self.m, self.m))[i]
		j = tuple(range(self.m))[j]
		return Array2dView(self.arr, i, j)

	def get_ind(self, i, j):
		return i * self.m + j

	def __getitem__(self, index):
		try:
			return self.arr[self.get_ind(*index)]
		except TypeError:
			return self._get_view(*index)

	def __setitem__(self, index, value):
		try:
			self.arr[self.get_ind(*index)] = value
		except TypeError:
			x = self._get_view(*index)
			for i in x.i_indices:
				for j in x.j_indices:
					self.arr[i + j] = value

	def __iter__(self):
		return iter(self.arr)

	def __reversed__(self):
		return reversed(self.arr)

	def __str__(self):
		m = max((len(str(v)) for v in self))
		res = [''] * self.n
		row = [''] * (self.m + 2)
		for i in range(self.n):
			if i == 0:
				row[0] = '['
			else:
				row[0] = ' '
			if i == self.n - 1:
				row[-1] = ']\n'
			for j in range(self.m):
				row[j + 1] = f'{str(self.arr[i * self.m + j]):>{m + 1}}'
			res[i] = ''.join(row)
		return '\n'.join(res)

	def __eq__(self, other):
		return self.arr == other.arr

	def copy(self):
		return self.__init__(self.n, self.m, self.arr[:])

	@property
	def t(self):
		arr = [self.arr[0]] * len(self.arr)
		x = 0
		for i in range(self.n):
			for j in range(self.m):
				arr[j * self.n + i] = self.arr[x]
				x += 1
		return self.__init__(self.m, self.n, arr)

def helper(n, m, queries):
	grid = Array2d.full(n, m, 0)
	cnt = 0
	for s in range(1, min(n, m) + 1):
		cnt += (n - s) * (m - s) * 2 + (n - s) * (m - s + 1) + (n - s + 1) * (m - s)
	cnt += n * m
	res = [cnt]
	for (i, j) in queries:
		ul = 0
		(x, y) = (i, j - 1)
		f = True
		while x >= 0 and y >= 0 and (not grid[x, y]):
			ul += 1
			if f:
				x -= 1
			else:
				y -= 1
			f = not f
		rd = 0
		(x, y) = (i + 1, j)
		f = True
		while x < n and y < m and (not grid[x, y]):
			rd += 1
			if f:
				y += 1
			else:
				x += 1
			f = not f
		lu = 0
		(x, y) = (i - 1, j)
		f = False
		while x >= 0 and y >= 0 and (not grid[x, y]):
			lu += 1
			if f:
				x -= 1
			else:
				y -= 1
			f = not f
		dr = 0
		(x, y) = (i, j + 1)
		f = False
		while x < n and y < m and (not grid[x, y]):
			dr += 1
			if f:
				y += 1
			else:
				x += 1
			f = not f
		k = (ul + 1) * (rd + 1) + (lu + 1) * (dr + 1) - 1
		r = res[-1]
		if not grid[i, j]:
			res.append(r - k)
			grid[i, j] = 1
		else:
			res.append(r + k)
			grid[i, j] = 0
	return res[1:]
(n, m, q) = map(int, input().split())
queries = [tuple((int(c) - 1 for c in input().split())) for _ in range(q)]
print(*helper(n, m, queries), sep='\n')


import collections
import math
import itertools
import sys
import time
import random

def fast_input():
	return sys.stdin.readline().strip()
input = fast_input

def ints_input():
	return list((int(x) for x in input().split()))

def int_input():
	return int(input())

def solve():
	(n, m, q) = ints_input()
	free = [[1 for _ in range(m)] for _ in range(n)]
	staircases_on_diagonal = [0 for _ in range(-m, n)]
	total_non_singleton_staircases = 0
	total_singleton_staircases = n * m

	def calculate_staircases(x):
		if x <= 0:
			start_point = (0, -x)
		else:
			start_point = (x, 0)
		staircases = 0
		if start_point[0] > 0:
			running = free[start_point[0] - 1][start_point[1]]
		else:
			running = 0
		while True:
			if free[start_point[0]][start_point[1]]:
				running += 1
			else:
				running = 0
			if running > 1:
				staircases += running - 1
			start_point = (start_point[0], start_point[1] + 1)
			if start_point[1] >= m:
				break
			if free[start_point[0]][start_point[1]]:
				running += 1
			else:
				running = 0
			if running > 1:
				staircases += running - 1
			start_point = (start_point[0] + 1, start_point[1])
			if start_point[0] >= n:
				break
		return staircases
	for x in range(-(m - 1), n):
		stairs = calculate_staircases(x)
		staircases_on_diagonal[x] = stairs
		total_non_singleton_staircases += stairs
	for _ in range(q):
		(x, y) = ints_input()
		x = x - 1
		y = y - 1
		free[x][y] = 1 - free[x][y]
		total_singleton_staircases += 1 if free[x][y] else -1
		for diff in (x - y, x + 1 - y):
			if diff < -(m - 1) or diff >= n:
				continue
			stairs = calculate_staircases(diff)
			total_non_singleton_staircases -= staircases_on_diagonal[diff]
			staircases_on_diagonal[diff] = stairs
			total_non_singleton_staircases += stairs
		print(total_non_singleton_staircases + total_singleton_staircases)
if False:
	for _ in range(int_input()):
		solve()
else:
	solve()