픽셀의 승리

2014년 3월 8일, 프랑스 파리의 현대미술관에서 대담한 절도 사건이 일어났습니다. 도둑들은 많은 전시품을 훔쳐 갔고, 그중 가장 유명한 작품은 사이버큐비스트 에티엔 부르시에-무주노의 그림 「픽셀의 승리」입니다.

미술관장 파브리스 에로트는 이렇게 말했습니다. "이것은 우리에게 큰 손실입니다. 경찰이 범인을 쫓고 있지만, 보안 시스템을 그토록 쉽게 뚫은 것을 보면 상대는 최고 수준의 전문가입니다. 그래서 이 걸작이 우리 소장품으로 돌아오리라고는 기대하지 않습니다. 또 미술관 데이터베이스가 전부 파괴되어 복원가들에게 그림을 되살릴 정보가 부족합니다. 프랑스 사람이라면 누구나 아는 사실이지만, 이 그림은 검은색과 흰색 정사각형 픽셀로 이루어진 $H \times W$ 직사각형입니다. 여기서 $H$는 높이, $W$는 너비이며 단위는 픽셀입니다. 다만 개별 픽셀의 색은 조금씩 찾아내야 합니다."

국립기록보관소의 아르멜 르 고프 대변인은 서둘러 대중을 안심시켰습니다. "다행히 기록보관소에는 그림의 일부 조각을 찍은 사진이 있습니다. 그림의 변과 평행한 직사각형 조각 $N$개에 대한 정보가 있고, 각 조각의 좌표 $r_1, c_1, r_2, c_2$와 포함된 픽셀의 색을 알고 있습니다. 다만 일부 조각은 반전된 상태로 보관되어 있을 수 있습니다. 즉 흰 픽셀은 검은색으로, 검은 픽셀은 흰색으로 바뀌어 있습니다. 어떤 조각이 반전되었는지는 확실하지 않습니다. 이 때문에 잃어버린 걸작을 복원하기가 훨씬 어렵습니다. 그래서 프로그래밍 커뮤니티에 도움을 청합니다. 기록보관소는 가진 조각 데이터를 모두 제공하겠습니다. 그림을 하나로 확정하지 못할 수도 있다는 점은 알고 있습니다. 따라서 가능한 그림 중 가장 밝은 그림, 즉 흰 픽셀이 가장 많은 그림을 찾아 주십시오. 「픽셀」은 부르시에-무주노의 작품 가운데 가장 낙관적인 작품으로 널리 알려져 있습니다."

첫 줄에는 그림의 높이 $H$와 너비 $W$가 주어집니다 ($1 \le H \cdot W \le 10^6$). 둘째 줄에는 조각의 개수 $N$ ($1 \le N \le 10^6$)이 주어집니다.

각 조각은 $r_1, c_1, r_2, c_2$ ($1 \le r_1 \le r_2 \le H$, $1 \le c_1 \le c_2 \le W$)가 적힌 줄로 시작합니다. 행은 위에서 아래로 1부터 $H$까지, 열은 왼쪽에서 오른쪽으로 1부터 $W$까지 번호가 매겨집니다. $(r_1, c_1)$은 조각의 왼쪽 위 픽셀, $(r_2, c_2)$는 오른쪽 아래 픽셀입니다. 이어서 $r_2 - r_1 + 1$개의 줄에 각각 $c_2 - c_1 + 1$개의 값이 공백으로 구분되어 나옵니다. 0은 흰 픽셀, 1은 검은 픽셀을 뜻합니다. 값은 보관된 상태 그대로이므로 반전되어 있을 수 있습니다.

모든 조각의 넓이 합 $S$는 $10^6$을 넘지 않습니다.

주어진 데이터를 모두 만족하는 그림이 없다면, 즉 기록보관소의 데이터가 서로 모순된다면 -1 한 개를 출력합니다.

그렇지 않다면 첫 줄에 잃어버린 그림이 가질 수 있는 0의 최대 개수를 출력합니다. 이어서 $H$개의 줄에 조각과 같은 형식으로, 0과 1을 공백으로 구분한 $W$개의 값을 한 줄씩 출력합니다. 흰 픽셀이 가장 많은 그림을 출력합니다. 흰 픽셀 수가 최대인 그림이 여러 개라면 그중 아무거나 출력해도 됩니다.

첫 번째 테스트에서 흰 픽셀의 최대 개수는 5입니다. 두 번째와 세 번째 조각을 반전하고, 어떤 조각으로도 덮이지 않은 유일한 픽셀을 흰색으로 칠하면 됩니다.