원통 게임의 즐거움

원통 게임은 아직 어디에도 공개되지 않은 새 게임이다. 이 게임을 만든 사람은 공개하기 전에 최적의 진행을 찾아 주는 프로그램을 먼저 갖추고 싶어 한다.

게임판은 원통이다. 원통은 위에서부터 $1$번부터 $N$번까지 번호가 붙은 $N$개의 행으로 나뉘고, 각 행은 다시 $1$번부터 $M$번까지 번호가 붙은 $M$개의 칸으로 나뉜다. 칸마다 수가 하나 적혀 있다. 게임판이 원통이므로 같은 행의 $1$번 칸과 $M$번 칸은 서로 붙어 있다.

칸은 두 수 $X$와 $Y$로 나타낸다. $X$는 행 번호이고 $Y$는 그 행에서의 칸 번호다. 두 칸 $(X_1, Y_1)$과 $(X_2, Y_2)$ 사이의 거리는 다음과 같다.

$|X_1 - X_2| + \min(|Y_1 - Y_2|, M - |Y_1 - Y_2|)$

게임은 첫 번째 행에서 아무 칸이나 하나 골라 시작한다. 그다음부터는 현재 칸에서 다음 행의 칸으로 옮겨 가는데, 두 칸 사이의 거리가 $K$를 넘지 않아야 한다. 마지막 행에 닿을 때까지 이 이동을 반복한다. 점수는 고른 칸에 적힌 수를 모두 더한 값이고, 이 점수를 최대로 만들어야 한다.

입력은 여러 개의 테스트 케이스로 이루어진다. 첫째 줄에 테스트 케이스의 개수 $T$가 주어진다($1 \le T \le 100$). 그 뒤로 $T$개의 테스트 케이스가 이어진다.

각 테스트 케이스는 $N + 1$개의 줄로 주어진다. 첫째 줄에는 행의 개수 $N$, 한 행의 칸 개수 $M$, 한 번의 이동에서 허용되는 최대 거리 $K$가 정수로 주어진다($1 \le N, M, K \le 1000$).

이어지는 $N$개의 줄에는 각각 $M$개의 수가 주어진다. $i$번째 줄의 $j$번째 수는 칸 $(i, j)$에 적힌 수다. 주어지는 모든 수의 절댓값은 $1000$ 이하다.

각 테스트 케이스마다 한 줄을 출력한다. 먼저 얻을 수 있는 최대 점수를 출력하고, 공백 하나를 둔 다음 $N$개의 수를 공백 하나씩으로 구분해 출력한다. $i$번째 수는 $i$번째 행에서 고른 칸의 번호다.

최대 점수를 얻는 방법이 여러 가지면 사전순으로 가장 앞서는 것을 출력한다. 두 답 $X$와 $Y$가 처음으로 달라지는 자리에서 $X$의 수가 더 작으면 $X$가 $Y$보다 사전순으로 앞선다.

연속한 두 행의 행 번호 차이는 항상 $1$이므로, $i$번째 행의 $y$번 칸에서 $i + 1$번째 행의 $y'$번 칸으로 가는 이동은 $\min(|y - y'|, M - |y - y'|) \le K - 1$일 때만 허용된다. 따라서 $K = 1$이면 칸 번호를 끝까지 바꿀 수 없다.

모든 행에서 정확히 한 칸씩 고르므로 출력하는 칸 번호는 항상 $N$개다.