Joy of the Cylinder Game

The cylinder game is new and has not been published anywhere yet. Its inventor wants a program that finds the best play before releasing the game.

The board is a cylinder. It is divided into $N$ rows numbered $1$ through $N$ starting at the top, and each row is divided into $M$ cells numbered $1$ through $M$. Every cell holds one number. Because the board is a cylinder, cell $1$ and cell $M$ of the same row are adjacent.

A cell is given by two numbers $X$ and $Y$, where $X$ is the row number and $Y$ is the cell number inside that row. The distance between cells $(X_1, Y_1)$ and $(X_2, Y_2)$ is

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

The game starts by picking any cell of the first row. From the current cell you then move to any cell of the next row whose distance from the current cell is at most $K$, and you repeat that move until you reach the last row. Your score is the sum of the numbers in the cells you picked, and the goal is to make that score as large as possible.

The input holds one or more test cases. The first line contains a single integer $T$, the number of test cases ($1 \le T \le 100$). The specifications of the $T$ test cases follow.

Each case takes $N + 1$ lines. The first line of a case contains three integers $N$, $M$ and $K$: the number of rows, the number of cells in each row, and the largest distance allowed in one move ($1 \le N, M, K \le 1000$).

Each of the remaining $N$ lines contains $M$ numbers. The $j$-th number on the $i$-th line is the number in cell $(i, j)$. Every given number has absolute value at most $1000$.

For each test case print one line. Start with the maximum score you can get, then a single space, then $N$ numbers separated by single spaces, where the $i$-th number is the index of the cell you picked in row $i$.

If several selections reach the same maximum score, print the lexicographically smallest one. A selection $X$ is lexicographically smaller than a selection $Y$ if $X$ has the smaller number at the first position where the two differ.

The row numbers of two consecutive rows always differ by $1$, so a move from cell $y$ of row $i$ to cell $y'$ of row $i + 1$ is allowed exactly when $\min(|y - y'|, M - |y - y'|) \le K - 1$. With $K = 1$ the cell number never changes.

Exactly one cell is picked in every row, so the printed list always holds $N$ numbers.