시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 86 19 19 33.333%

문제

규민이는 각 칸에 음이 아닌 정수가 적힌 NM 격자를 하나 가지고 있다. 

이제 규민이는 각 칸에 적힌 정수들을 모두 0으로 만들고자 하고, 이를 위해 규민이는 다음과 같은 시행을 할 수 있다. 

  • 시행: 격자에서 인접한 두 칸을 선택하고, 정수 k를 선택한다. 인접한 두 칸에 적힌 수에 k를 더한다.

단, 시행 이후에도 격자에 적힌 모든 수는 항상 음이 아닌 정수이도록 한다. 또한, 두 칸이 '인접하다'는 것은, 두 칸이 서로 변을 하나 공유하고 있다는 뜻이다. 

규민이가 가지고 있는 NM 격자에 대한 정보가 주어졌을 때, 규민이가 시행을 통해 목표를 달성할 수 있는지 판별하자.

입력

첫째 줄에 격자의 세로 길이 N과 가로 길이 M이 주어진다. (2 ≤ N, M ≤ 500)

둘째 줄부터 N+1번째 줄까지, 규민이가 가지고 있는 격자에 적혀 있는 수들이 한 줄에 M개씩 주어진다.

주어지는 각 정수는 음이 아닌 정수로, 106 이하인 정수이다. 

출력

만약 규민이가 목표를 달성할 수 없다면, -1을 출력한다. 

규민이가 목표를 달성할 수 있다면, 규민이가 목표를 달성할 수 있는 방법을 아래에 주어진 형식으로 출력한다.

첫째 줄에는 규민이의 시행 횟수 X를 출력한다. 단, 0 ≤ X ≤ 106를 만족해야 한다.

둘째 줄부터 X+1번째 줄에는, i번째 줄에 규민이가 실행하는 i-1번째 시행에 대한 정보를 r1 c1 r2 c2 k 형식으로 출력한다.

여기서 (r1, c1)과 (r2, c2)는 규민이가 선택한 인접한 두 칸의 좌표이고, 1 ≤ r1, r2 ≤ N과 1 ≤ c1, c2 ≤ M, 그리고 |r1-r2|+|c1-c2|=1을 만족한다.

또한, k는 규민이가 시행을 통해 두 칸에 적힌 수에 더할 정수로, -1012 ≤ k ≤ 1012가 성립해야 한다. 

규민이의 시행 횟수를 최소화할 필요는 없음에 주의하라. 

또한, 규민이가 목표를 달성할 수 있다면, 주어진 출력 조건을 만족하는 방법으로 목표를 달성할 수 있음이 보장된다. 

예제 입력 1

2 2
3 5
7 9

예제 출력 1

5
1 1 1 2 4
1 1 2 1 -5
1 1 1 2 -2
1 2 2 2 -7
2 1 2 2 -2

예제 입력 2

3 5
87 153 46 362 54
52 631 157 246 265
266 351 437 235 135

예제 출력 2

-1