Задача E. Укладка плиток ≡

Условие

Вы являетесь одним из разработчиков нового архитектурного пакета прикладных программ CadArch. Одной из его функций является проектирование укладки половых плиток. В настоящее время вы занимаетесь программной реализацией модуля, который отвечает за укладку плиток в прямоугольных помещениях.

Для простоты будем считать, что пол помещения представляет собой прямоугольник размером n на m метров, разбитый на m*n квадратиков со стороной по 1 метру. Кроме этого, будем считать, что имеется четыре типа плиток, показанные в таблице. Каждая из плиток представляет собой квадрат размером 2 на 2 метра, из которого вырезан один квадратик размером 1 на 1 метр.

1	2
3	4

Проектируемый модуль должен работать следующим образом. На вход модуля подается набор команд, каждая из которых обозначает, в какое место и какого типа плитку необходимо положить. Команда обрабатывается следующим образом: если ни один из квадратиков, который должна занимать текущая плитка, не занят и плитка полностью помещается внутри прямоугольника, то плитка размещается в указанном месте, в противном случае — нет.

Требуется написать программу, которая определяет, какая площадь в соответствии с заданным набором команд будет покрыта плитками.

Формат входного файла

Первая строка входного файла содержит два числа m и n - размеры пола помещения.

Вторая строка содержит число k — количество команд, которые необходимо обработать. Каждая из последующих k строк содержит описание одной команды из набора команд. Описание команды состоит из трех чисел. Первое число определяет тип плитки (число от 1 до 4), а два других координаты левого верхнего квадрата размером 2 на 2, в который вписана соответствующая плитка.

Формат выходного файла

В выходной файл необходимо вывести одно число, определяющее площадь, покрытую плитками после выполнения заданной во входном файле последовательности команд.

Ограничения

1 ≤ m, n ≤ 50

0 ≤ k ≤ 1000

Примеры тестов

4 4
4
4 1 1
2 2 2
3 1 1
1 3 3

9