양파깡 만들기

양파깡은 가운데가 비어 있는 직사각형 테두리 모양의 과자이다. 하나의 양파깡은 높이와 너비가 모두 3 이상인, 격자에 평행한 직사각형의 테두리 칸들로 이루어진다. 직사각형의 내부 칸들은 양파깡에 포함되지 않는다.

N × N 크기의 과자판이 주어진다. 각 칸에는 정수가 적혀 있으며, 양수는 기준보다 양념이 많이 뿌려졌음을, 음수는 기준보다 적게 뿌려졌음을 뜻한다. 양파깡의 맛은 그 테두리에 포함된 칸들의 값의 합으로 정의된다.

작업은 M번 반복된다. 매 단계마다 아직 잘려 나가지 않은 칸만 사용해서 만들 수 있는 양파깡 중 맛이 가장 큰 것을 하나 고르고, 그 테두리 칸들을 잘라낸다. 서로 다른 양파깡의 테두리는 겹칠 수 없다. 내부 칸은 양파깡의 일부가 아니므로, 나중에 만드는 양파깡의 내부에 이전에 잘려 나간 칸이 들어 있어도 된다.

잘라낸 순서대로 각 양파깡의 맛과 위치를 출력하라. M개를 모두 잘라낼 수 없다면 0을 출력한다.

첫 줄에 과자판의 크기 N과 잘라낼 양파깡의 개수 M이 주어진다.

다음 N개의 줄에는 과자판을 나타내는 정수 N개가 한 줄에 하나씩 주어진다.

잘라낸 순서대로 양파깡 하나당 한 줄씩, 총 M줄을 출력한다.

각 줄에는 양파깡의 맛, 왼쪽 위 칸의 행과 열, 오른쪽 아래 칸의 행과 열을 이 순서대로 출력한다.

좌표는 1부터 시작한다. 조건을 만족하며 양파깡 M개를 잘라낼 수 없다면 한 줄에 0만 출력한다.

가능한 답이 여러 가지라면 그중 아무거나 출력해도 된다.

• 3 ≤ N ≤ 30
• 1 ≤ M ≤ 30
• 각 양념 값은 -100 이상 100 이하의 정수이다.