| Codeforces Round 296 (Div. 2) |
|---|
| Закончено |
Леонид хочет стать резчиком по стеклу. У него уже есть прямоугольный лист стекла w мм × h мм, алмазный стеклорез и полные штаны энтузиазма. Не хватает только понимания, что и как резать.
Чтобы не терять времени даром, он решил поупражняться в технике разрезов. Для этого он проводит вертикальные и горизонтальные разрезы через весь лист. В результате этого процесса образуются меньшие прямоугольные куски стекла. Леонид не перемещает образовавшиеся куски стекла, в частности, очередной разрез делит на меньшие части каждый кусок стекла, через который он проходит.
После каждого разреза Леонид пытается определить, какую площадь имеет самый большой из имеющихся на данный момент фрагментов стекла. Так как частей становится всё больше и больше, этот вопрос занимает у него всё больше и больше времени, и отвлекает от увлекательного процесса.
Леонид предлагает устроить разделение труда — он будет резать стекло, а вы — считать площадь максимального фрагмента после каждого разреза. Идёт?
В первой строке заданы три целых числа w, h, n (2 ≤ w, h ≤ 200 000, 1 ≤ n ≤ 200 000).
В последующих n строках следуют описания разрезов. Каждое описание имеет вид H y или V x. В первом случае проводится горизонтальный разрез на расстоянии y миллиметров (1 ≤ y ≤ h - 1) от нижнего края исходного листа, во втором случае проводится вертикальный разрез на расстоянии x (1 ≤ x ≤ w - 1) миллиметров от левого края исходного листа. Гарантируется, что Леонид не будет производить два одинаковых разреза.
После каждого разреза выводите в отдельной строке площадь максимального из имеющихся фрагментов стекла в квадратных миллиметрах.
4 3 4
H 2
V 2
V 3
V 1
8
4
4
2
7 6 5
H 4
V 3
V 5
H 2
V 1
28
16
12
6
4
Пояснение к первому тесту из условия:
