Эпидемия гриппа не обошла стороной семиклассника Алешу. Скучая дома, Алеша решил вырезать фигурки из листа клетчатой бумаги. Лист состоял из M строк и N столбцов клеточек. Сначала Алеша нарисовал на листе границы фигур. Количество фигур было не меньше 2. Чтобы фигуры получались ровными, границы фигур Алеша рисовал строго по линиям имеющейся клеточной разметки листа (при этом некоторые границы фигур могли пройти по границам листа). Форма фигур могла быть любой, но при этом все фигуры были связными (фигура называется связной, если из любой ее клетки можно добраться до любой другой, ходя только по клеткам фигуры и перемещаясь каждый раз в одну из 4-х соседних по стороне клеток). Никакие две фигуры не имели общих точек, в том числе не касались углами клеток.
<>Затем Алеша вырезал нарисованные фигуры, делая разрезы только по их границам. При этом оставшаяся часть листа осталась связной (то есть не распалась на несколько частей).
Лист с вырезами Алеша отсканировал. Сканер в своей памяти по результатам сканирования построил таблицу, состоящую из нулей и единиц, из M строк и N столбцов (строки нумеруются сверху вниз от 1 до M, столбцы — слева направо от 1 до N). Каждый элемент таблицы соответствовал клеточке исходного листа. Единица обозначала, что соответствующая клетка листа осталась на месте, ноль — соответствующая клетка была вырезана.
На рис. 1 приведен пример клетчатого листа, а на рис. 2 — соответствующая ему таблица в памяти сканера:
Рис 1.
Исходный клеточный лист с вырезанными фигурами
Размер листа: M=6, N=12.
Количество вырезанных фигур: 3 |
| 1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
| 1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
| 1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
| 1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
| 1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
| 1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Рис 2.
Такая таблица строится в памяти сканера
|
После этого сканер представил полученную таблицу в специальном, описанном ниже формате и передал информацию на компьютер. Напишите программу, которая по полученной информации установит:
Пункт 1. Сколько клеток было вырезано из листа?
Пункт 2. Сколько фигур было вырезано? Описание формата представления таблицы Последовательность подряд идущих по горизонтали или вертикали единиц будем называть полосой. Полосу можно задаеть 4 числами:
- направление (0—горизонтальная, 1—вертикальная)
- (i, j) — координаты начальной клетки полосы (начальной является самая левая клетка для горизонтальной полосы, и самая верхняя — для вертикальной), i — номер строки клетки, j — номер столбца
- d — длина полосы (количество подряд стоящих единиц).
Всю таблицу разобьем на полосы, состоящие из единиц так, чтобы каждая единица принадлежала хотя бы одной полосе. При этом полосы могут пересекаться, а также накладываться. Таким образом, таблица представляется в виде описания всех полос, которое удовлетворяет трем дополнительным требованиям:
- В каждой клетке начинается не более одной полосы.
- Полосы перечислены в порядке следования их начальных клеток (клетки перечисляются по строкам сверху вниз, в строке — слева направо).
- Общее число полос не превышает 256000.
Заметим, что таблица может быть представлена в виде полос разными способами, но каждое представление позволяет однозначно восстановить таблицу.
Входные данные
Во входном файле записано сначала число P (1 или 2) — номер пункта задачи, ответ на который требуется получить. Далее записаны размеры исходного листа — числа M и N (1 ≤ M ≤ 4000,1 ≤ N ≤ 4000) . Затем записано число K (0 ≤ K ≤ 256000) — количество полос в описании полученной таблицы. Затем идет K четверок чисел, описывающих полосы (полосы перечисляются в порядке начальных клеток полос: по строкам сверху вниз, в строке — слева направо).
Выходные данные
В выходной файл выведите искомое количество (если P=1, то — количество клеток, вырезанных из листа, если P=2, то — количество фигур, вырезанных из листа).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
40 400
2
1 1 100 40
0 1 101 1
|
15959
|
|
2
|
2
40 400
2
1 1 100 40
1 1 101 1
|
2
|