16711번 - Erasing Matrix 스페셜 저지

문제

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

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

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

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

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

입력

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

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

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

출력

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

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

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

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

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

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

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

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

제한

힌트