1625번 - 조명기구 스페셜 저지

철수는 전등이 N × M의 그리드 형태로 배열된 조명기구를 가지고, 연극에서 전등이 내는 색을 조절하는 조명감독의 역할을 맡았다. 전등은 빨간색과 하얀색 두 가지 색중 하나의 색을 가지고 있다. 그리고 조명기구의 각 행에는 하나의 행 버튼이 있어서 버튼을 누르면 그 행에 있는 모든 전등의 색이 바꾸어진다. 즉, 각 전등의 색이 빨간색이면 하얀색으로 바꾸어지고, 하얀색이면 빨간색으로 바꾸어진다. 또한 조명기구의 각 열에는 하나의 열 버튼이 있어서 두 개의 열 버튼을 동시에 누르면 각 열 버튼에 있는 두 개의 열이 전등의 순서를 바꾸지 않고 서로 교환된다고 한다.

예를 들어, 다음 그림 (a)와 같이 4 × 5의 그리드 형태의 조명기구가 주어진다고 하자. 이때, 0은 하얀색, 1은 빨간색을 나타낸다. 그림 (a)에서 두 번째 행에 있는 행 버튼을 누르면, 두 번째 행의 색이 바꾸어져서 그림 (b)와 같이 되고, 그림 (b)에서 다시 두 번째 열과 네 번째 열의 버튼을 동시에 누르면 두 번째 열과 네 번째 열이 서로 교환되어 그림 (c)와 같은 전등의 색을 얻을 수 있다.

01001
10110
01110
10101

01001
01001
01110
10111

00011
00011
01110
11101

N × M 조명기구의 초기의 전구 색과 최종 전구 색이 주어졌을 때, 행 버튼과 열 버튼을 사용하여 초기의 전구 색에서 최종 전구 색으로 변환하는 프로그램을 작성하시오.

입력 파일의 첫째 줄에 조명기구의 행과 열의 크기를 나타내는 두 정수 N, M이 빈칸을 사이에 두고 주어지고, 둘째 줄부터 다음 N개의 줄에는 각 줄마다 초기 전등의 색을 나타내는 M개의 수(0 또는 1)가 주어지고, 다음 줄부터 N개의 줄에는 각 줄마다 최종 전등의 색을 나타내는 M개의 수(0 또는 1)가 빈칸을 사이에 두고 주어진다. 둘째 줄부터 다음 N개의 줄에서 i번째 줄의 j번째 수는 조명기구에서 i번째 행의 j번째 열의 초기 전구의 색을 나타낸다. 마찬가지로, 다음 줄부터 다음 N개의 줄에서 i번째 줄의 j번째 수는 조명기구에서 i번째 행의 j번째 열의 최종 전구의 색을 나타낸다. 0는 하얀색을, 1은 빨간색을 각각 표시한다.

출력 파일의 첫째 줄에 초기 전구의 색에서 최종 전구의 색으로 변환이 되지 않으면 -1을 출력하고, 아니면 출력 파일의 첫째 줄에 행 버튼을 눌러 행의 전구 색을 바꾸는 횟수(=R)와 열 버튼을 눌러 두개의 열을 교환하는 횟수(=C)의 총합 S(=R+C)를 출력하고, 둘째 줄부터 다음 S개의 줄에는 버튼을 누른 순서대로 다음과 같은 방식으로 출력한다. 둘째 줄에는 처음에 행 버튼 i를 눌러 행의 색을 바꾸었을 경우 두개의 정수 0, i를 빈 칸을 사이에 두고 출력하고, 열 버튼 i와 j를 눌러 열을 교환 했을 경우 세 개의 정수 1, i, j를 빈 칸을 사이에 두고 출력한다. 마찬가지로 k+1번째 줄에는 k번째에 행 버튼 i를 눌러 행의 색을 바꾸었을 경우 두개의 정수 0, i를 빈 칸을 사이에 두고 출력하고, 열 버튼 i와 j를 눌러 열을 교환 했을 경우 세 개의 정수 1, i ,j를 빈 칸을 사이에 두고 출력한다.

한 행 버튼은 최대 두 번 누를 수 있고, 같은 열 버튼의 조합도 최대 두 번 누를 수 있다.

• 1 ≤ N ≤ 256
• 1 ≤ M ≤ 256