Задача №112094. Пиксели торжествуют
08.03.2014, Париж, Франция. Дерзкое ограбление совершено в Парижском музее современного искусства. Похищено множество экспонатов, наиболее известный из которых — картина «Пиксели торжествуют» киберкубиста Этьена Бурсье-Мужено.
«Это большая потеря для нас, — заявил директор музея Фабрис Эрготт. — Полиция уже разыскивает преступников, но мы вынуждены признать, что, судя по тому, как легко злоумышленники справились с охранной системой, мы имеем дело с профессионалами экстра-класса и не питаем надежд на возвращение шедевра в нашу коллекцию. Кроме того, уничтожена вся база данных музея, поэтому реставраторы не обладают достаточным количеством информации для восстановления картины. Безусловно, каждый образованный француз знает, что она представляет собой прямоугольник из \(H\) x \(W\) черных и белых квадратных пикселей (\(H\) — высота, а \(W\) — ширина картины в пикселях). Но информацию о цвете самих пикселей придется добывать по крупицам».
В свою очередь, представитель Национального архива Франции Армель Ле Гофф поспешила успокоить культурную общественность: «К счастью, архив располагает снимками отдельных фрагментов картины. А именно, в нашем распоряжении имеется информация о \(N\) прямоугольных фрагментах (со сторонами, параллельными соответствующим сторонам картины), для каждого из которых известны его координаты \(r_1\), \(c_1\), \(r_2\), \(c_2\), а также цвета входящих в него пикселей. Строки картины пронумерованы от 1 до \(H\) сверху вниз, столбцы — от 1 до \(W\) слева направо, (\(r_1\); \(c_1\)) — номера строки и столбца левого верхнего пикселя фрагмента, (\(r_2\); \(c_2\)) — номера строки и столбца правого нижнего пикселя фрагмента, \(r_1\) ≤ \(r_2\), \(c_1\) ≤ \(c_2\). Однако, в силу ряда причин некоторые фрагменты могут храниться в инвертированном виде, то есть все белые пиксели в них заменены на черные, а все черные — на белые, при этом достоверно не известно, какие фрагменты инвертированы. Это серьезно усложняет задачу по восстановлению утерянного шедевра величайшего киберкубиста, поэтому мы обращаемся за помощью ко всему программистскому сообществу. Национальный архив, со своей стороны, готов предоставить все имеющиеся данные о фрагментах картины. Мы отдаем себе отчет в том, что, возможно, картину не удастся восстановить однозначно, поэтому просим найти максимально светлую из всех возможных подходящих картин, то есть содержащую как можно больше белых пикселей: широко известно, что „Пиксели“ являются одним из самых оптимистичных творений Этьена Бурсье-Мужено».
Первая строка входного файла содержит два целых числа \(H\) и \(W\) (1 ≤ \(H\) * \(W\) ≤ \(10^6\)) — высоту и ширину картины в пикселях. Вторая строка содержит единственное целое число \(N\) (1 ≤ \(N\) ≤ \(10^6\)) — количество фрагментов. Далее содержатся \(N\) описаний фрагментов. Первая строка описания — координаты \(r_1\), \(c_1\), \(r_2\), \(c_2\) (1 ≤ \(r_1\) ≤ \(r_2\) ≤ \(H\), 1 ≤ \(c_1\) ≤ \(c_2\) ≤ \(W\)). Следующие \(r_2\) - \(r_1\) + 1 строк описания содержат сам фрагмент (возможно, инвертированный): каждая из этих строк состоит из ровно \(c_2\) - \(c_1\) + 1 нулей и единиц, разделенных пробелами. Нули означают белые пиксели, единицы - черные.
Суммарная площадь всех фрагментов \(S\) ≤ \(10^6\).
Если подходящей картины не существует, то~есть предоставленные Национальным архивом данные противоречивы, выведите единственное число \(-1\).
Иначе в первой строке выходного файла выведите максимальное число нулей, которое могла содержать утерянная картина, а в следующих \(H\) строках — искомую картину с максимально возможным количеством нулей в том же формате, что и фрагменты во входном файле: \(H\) строк, в каждой из которых \(W\) разделенных пробелами нулей и единиц. Если подходящих картин с максимальным числом белых пикселей несколько, выведите любую из них.
В первом тесте из условия максимально возможное количество белых пикселей равно 5. А именно, нужно инвертировать второй и третий фрагменты, а единственный пиксель, не покрытый фрагментами, покрасить в белый цвет:
Тесты к этой задаче состоят из четырех групп.
0. Тесты 1–2. Тесты из условия, оцениваются в ноль баллов.
1. Тесты 3–27. В тестах этой группы \(N\) ≤ 10, \(S\) ≤ 1 000, \(H\) * \(W\) ≤ 1 000. Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
2. Тесты 28–36. В тестах этой группы \(N\) ≤ 500, \(S\) ≤ 20 000, \(H\) * \(W\) ≤ 500 000. Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы. Решение будет тестироваться на тестах этой группы только в случае прохождения всех тестов из первой группы.
3. Тесты 37–39. В тестах этой группы \(S\) ≤ 20 000, \(H\) * \(W\) ≤ 500 000. Эта группа оценивается в 4 балла, баллы начисляются только при прохождении всех тестов группы. Решение будет тестироваться на тестах этой группы только в случае прохождения всех тестов из первой и второй групп.
4. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 36 баллов. Решение будет тестироваться на тестах этой группы только в случае прохождения всех тестов из первой, второй и третьей групп. Тесты в этой группе оцениваются независимо.
2 3 3 1 1 1 2 0 1 1 2 2 2 0 1 1 3 2 3 1 1
5 0 1 0 0 0 0
2 3 2 1 2 2 3 0 1 1 0 1 1 1 3 0 1 1
-1