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

Автор:Методическая комиссия по информатике   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

Вы являетесь одним из разработчиков нового архитектурного пакета прикладных программ 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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4 4
4
4 1 1
2 2 2
3 1 1
1 3 3
9

0.045s 0.007s 23