420. Упаковка эчпочмаков

Андрей работает мыловаром и живет в общежитии со своим соседом Азатом. Бабушка прислала Азату коробку своих фирменных эчпочмаков. Эчпочмаки пахли так вкусно, что Андрей не выдержал и съел некоторые из них.

Коробка с эчпочмаками $-$ это прямоугольник размером $N \times M$. Фирменные эчпочмаки бабушки Азата представляют собой непересекающиеся равнобедренные треугольники, вершины которых имеют целые координаты (начало координат в левом нижнем углу коробки). Хотя бы одна сторона каждого эчпочмака параллельна стороне коробки.

Андрей решил оставить уцелевшие эчпочмаки на своих местах, а взамен съеденных приготовить новые и расположить их так, чтобы никакие два эчпочмака не пересекались и в коробке не осталось свободного места. Приготовленные Андреем эчпочмаки также должны быть равнобедренными треугольниками, их вершины должны иметь целочисленные координаты и хотя бы одна из сторон должна быть параллельна стороне коробки.

Определите минимальное количество эчпочмаков, которые должен приготовить Андрей и координаты, в которых их необходимо разместить. Если правильных ответов несколько $-$ выведите любой из них.

В первой строке вводится три целых числа $N$, $M$ и $K$ ($1 \le N, M \le 4$, $0 \le K \le 32$) $-$ размеры коробки и количество уцелевших эчпочмаков бабушки Азата.

Следующие $K$ строк содержат по 6 координат ($x1, y1$), ($x2, y2$), ($x3, y3$) ($0 \le x_i \le N$, $0 \le y_i \le M$).

Выведите число Ө $-$ минимальное количество эчпочмаков, которые должен приготовить Андрей.

В следующих Ө строках выведите по 6 чисел $-$ координаты эчпочмаков в том же формате, как во входных данных.

Если правильных ответов несколько $-$ выведите любой из них.

Рисунки соответствуют примерам. Эчпочмаки от бабушки покрашены в зеленый, а приготовленные Андреем имеют красный контур