Leonid wants to become a glass carver (the person who creates beautiful artworks by cutting the glass). He already has a rectangular w mm  ×  h mm sheet of glass, a diamond glass cutter and lots of enthusiasm. What he lacks is understanding of what to carve and how.

In order not to waste time, he decided to practice the technique of carving. To do this, he makes vertical and horizontal cuts through the entire sheet. This process results in making smaller rectangular fragments of glass. Leonid does not move the newly made glass fragments. In particular, a cut divides each fragment of glass that it goes through into smaller fragments.

After each cut Leonid tries to determine what area the largest of the currently available glass fragments has. Since there appear more and more fragments, this question takes him more and more time and distracts him from the fascinating process.

Leonid offers to divide the labor — he will cut glass, and you will calculate the area of the maximum fragment after each cut. Do you agree?


-----Input-----

The first line contains three integers w, h, n (2 ≤ w, h ≤ 200 000, 1 ≤ n ≤ 200 000).

Next n lines contain the descriptions of the cuts. Each description has the form H y or V x. In the first case Leonid makes the horizontal cut at the distance y millimeters (1 ≤ y ≤ h - 1) from the lower edge of the original sheet of glass. In the second case Leonid makes a vertical cut at distance x (1 ≤ x ≤ w - 1) millimeters from the left edge of the original sheet of glass. It is guaranteed that Leonid won't make two identical cuts.


-----Output-----

After each cut print on a single line the area of the maximum available glass fragment in mm^2.


-----Examples-----
Input
4 3 4
H 2
V 2
V 3
V 1

Output
8
4
4
2

Input
7 6 5
H 4
V 3
V 5
H 2
V 1

Output
28
16
12
6
4



-----Note-----

Picture for the first sample test:  [Image]  Picture for the second sample test:  $\square$

Source: codeforces | Difficulty: MEDIUM
Tags: Sorting

Data structures

Implementation


Solutions:
def main():
	from sys import stdin
	(w, h, n) = list(map(int, stdin.readline().split()))
	(res, vrt, hor) = ([], [], [])
	vh = (vrt, hor)
	for (i, s) in enumerate(stdin.read().splitlines()):
		x = int(s[2:])
		flag = s[0] == 'V'
		vh[flag].append(i)
		res.append([x, flag])
	dim = []
	for (tmp, m) in zip(vh, (h, w)):
		tmp.sort(key=lambda e: res[e][0])
		u = [None, [0]]
		dim.append(u)
		j = z = 0
		for i in tmp:
			x = res[i][0]
			if z < x - j:
				z = x - j
			j = x
			v = [u, res[i]]
			u.append(v)
			u = v
			res[i].append(u)
		v = [u, [m], None]
		u.append(v)
		dim.append(v)
		if z < m - j:
			z = m - j
		dim.append(z)
	(l, r, wmax, u, d, hmax) = dim
	whmax = [wmax, hmax]
	for i in range(n - 1, -1, -1):
		(x, flag, link) = res[i]
		u = whmax[flag]
		res[i] = u * whmax[not flag]
		link[0][2] = link[2]
		link[2][0] = link[0]
		v = link[2][1][0] - link[0][1][0]
		if u < v:
			whmax[flag] = v
	print('\n'.join(map(str, res)))

def __starting_point():
	main()
__starting_point()


import collections
import time
import os
import sys
import bisect
import heapq
from typing import List

class Node:
	val = None

	def __init__(self, val):
		self.val = val
		self.left = Node
		self.right = None

def solve(W, H, N, A):
	xs = [0] + [v for (t, v) in A if t == 0] + [W]
	ys = [0] + [v for (t, v) in A if t == 1] + [H]
	xs.sort()
	ys.sort()
	xlist = Node(0)
	h = xlist
	xnodes = {0: h}
	maxw = max([xs[i + 1] - xs[i] for i in range(len(xs) - 1)] or [0])
	maxh = max([ys[i + 1] - ys[i] for i in range(len(ys) - 1)] or [0])
	for v in xs[1:]:
		n = Node(v)
		xnodes[v] = n
		h.right = n
		n.left = h
		h = n
	ylist = Node(0)
	h = ylist
	ynodes = {0: h}
	for v in ys[1:]:
		n = Node(v)
		ynodes[v] = n
		h.right = n
		n.left = h
		h = n
	ans = []
	maxarea = maxh * maxw
	for (t, v) in reversed(A):
		ans.append(maxarea)
		if t == 0:
			node = xnodes[v]
			w = node.right.val - node.left.val
			maxw = max(maxw, w)
		else:
			node = ynodes[v]
			h = node.right.val - node.left.val
			maxh = max(maxh, h)
		node.left.right = node.right
		node.right.left = node.left
		maxarea = maxh * maxw
	return ans[::-1]

def solve2(W, H, N, A):
	ws = [(-W, 0, W)]
	hs = [(-H, 0, H)]
	(iw, ih) = (set(), set())
	ans = []
	(xs, ys) = ([0, W], [0, H])
	for (t, v) in A:
		if t == 0:
			bisect.insort_left(xs, v)
			i = bisect.bisect_left(xs, v)
			(l, m, r) = (xs[i - 1], xs[i], xs[i + 1])
			iw.add((l - r, l, r))
			heapq.heappush(ws, (l - m, l, m))
			heapq.heappush(ws, (m - r, m, r))
			while ws[0] in iw:
				heapq.heappop(ws)
		else:
			bisect.insort(ys, v)
			i = bisect.bisect_left(ys, v)
			(l, m, r) = (ys[i - 1], ys[i], ys[i + 1])
			ih.add((l - r, l, r))
			heapq.heappush(hs, (l - m, l, m))
			heapq.heappush(hs, (m - r, m, r))
			while hs[0] in ih:
				heapq.heappop(hs)
		(w, h) = (ws[0], hs[0])
		ans.append(w[0] * h[0])
	return ans
(W, H, N) = map(int, input().split())
A = []
for i in range(N):
	(a, b) = input().split()
	c = 0 if a == 'V' else 1
	A.append((c, int(b)))
print('\n'.join(map(str, solve(W, H, N, A))))


(w, h, n) = map(int, input().split())
x = [0, w]
y = [0, h]
rev = []
for _ in range(n):
	(s, d) = input().split()
	if s == 'H':
		y.append(int(d))
	else:
		x.append(int(d))
	rev.append((s, int(d)))
x.sort()
y.sort()
_max = 0
if len(x) > 1:
	for idx in range(len(x) - 1):
		_max = max(_max, x[idx + 1] - x[idx])
else:
	_max = w
max_x = _max
_max = 0
if len(y) > 1:
	for idx in range(len(y) - 1):
		_max = max(_max, y[idx + 1] - y[idx])
else:
	_max = w
max_y = _max
enum_x = {num: idx for (idx, num) in enumerate(x)}
enum_y = {num: idx for (idx, num) in enumerate(y)}
old_x = x
old_y = y
x = [[0, 0, 0]] * len(old_x)
y = [[0, 0, 0]] * len(old_y)
for idx in range(1, len(x) - 1):
	x[idx] = [old_x[idx], idx - 1, idx + 1]
for idx in range(1, len(y) - 1):
	y[idx] = [old_y[idx], idx - 1, idx + 1]
x[-1] = [w, 0, 0]
y[-1] = [h, 0, 0]
rev.reverse()
ans = [max_x * max_y]
for item in rev:
	if item[0] == 'H':
		elem = y[enum_y[item[1]]]
		max_y = max(max_y, y[elem[2]][0] - y[elem[1]][0])
		y[elem[1]][2] = elem[2]
		y[elem[2]][1] = elem[1]
	else:
		elem = x[enum_x[item[1]]]
		max_x = max(max_x, x[elem[2]][0] - x[elem[1]][0])
		x[elem[1]][2] = elem[2]
		x[elem[2]][1] = elem[1]
	ans.append(max_x * max_y)
ans.pop()
print('\n'.join(map(str, reversed(ans))))


from collections import defaultdict, Counter
import os
import sys
from io import BytesIO, IOBase
ii = lambda : int(input())
lmii = lambda : list(map(int, input().split()))
slmii = lambda : sorted(map(int, input().split()))
li = lambda : list(input())
mii = lambda : map(int, input().split())
msi = lambda : map(str, input().split())

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 gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	return a * b // gcd(a, b)

def main():
	(w, h, n) = mii()
	(ws, dws, hs, dhs, hsm, wsm) = (SortedList([]), defaultdict(int), SortedList([]), defaultdict(int), SortedList([]), SortedList([]))
	hsm.add(h)
	wsm.add(w)
	hs.add(0)
	ws.add(0)
	hs.add(h)
	ws.add(w)
	dhs[h] = 1
	dhs[0] = 1
	dws[0] = 1
	dws[w] = 1
	for i in range(n):
		(t, p) = map(str, input().split())
		p = int(p)
		if t == 'H':
			if dhs[p] == 0:
				hs.add(p)
				dhs[p] = 1
			ind = hs.bisect_left(p)
			(pre, nex) = (hs[ind - 1], hs[ind + 1])
			hsm.__delitem__(hsm.bisect_left(nex - pre))
			hsm.add(p - pre)
			hsm.add(nex - p)
		else:
			if dws[p] == 0:
				ws.add(p)
				dws[p] = 1
			ind = ws.bisect_left(p)
			(pre, nex) = (ws[ind - 1], ws[ind + 1])
			wsm.__delitem__(wsm.bisect_left(nex - pre))
			wsm.add(p - pre)
			wsm.add(nex - p)
		print(wsm[-1] * hsm[-1])
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


(w, h, n) = map(int, input().split())
l = [-1] * (w + 1)
r = [-1] * (w + 1)
t = [-1] * (h + 1)
b = [-1] * (h + 1)
l[0] = 0
b[0] = 0
t[h] = h
r[w] = w
V = [0] * n
H = [0] * n
for i in range(n):
	(line, index) = input().split()
	index = int(index)
	if line == 'V':
		r[index] = w
		V[i] = index
	else:
		t[index] = h
		H[i] = index
left = 0
mxw = 0
for i in range(1, w + 1):
	if r[i] != -1:
		l[i] = left
		r[left] = i
		mxw = max(mxw, i - left)
		left = i
bottom = 0
mxh = 0
for i in range(1, h + 1):
	if t[i] != -1:
		b[i] = bottom
		t[bottom] = i
		mxh = max(mxh, i - bottom)
		bottom = i
ans = [0] * n
ans[n - 1] = mxh * mxw
for i in range(n - 1, 0, -1):
	if V[i] != 0:
		mxw = max(mxw, r[V[i]] - l[V[i]])
		r[l[V[i]]] = r[V[i]]
		l[r[V[i]]] = l[V[i]]
	else:
		mxh = max(mxh, t[H[i]] - b[H[i]])
		b[t[H[i]]] = b[H[i]]
		t[b[H[i]]] = t[H[i]]
	ans[i - 1] = mxh * mxw
for i in range(n):
	print(ans[i])