Lista perdida#13113

Lista perdida

1 segundo
256 megabytes

Una estación de esquí tiene pistas de niveles de pendiente, numerados de a (un número mayor significa una pista más empinada), y niveles de longitud, numerados de a (un número mayor significa una pista más larga). Se dice que una pista con nivel de pendiente y nivel de longitud tiene tipo .

Cada esquiador tiene dos límites: el nivel máximo de pendiente y el nivel máximo de longitud que acepta esquiar (1 \le x \le n, 1 \le y \le m). Un esquiador con límites considera adecuada una pista de tipo si i \le x y j \le y. Distintos esquiadores pueden tener los mismos límites.

La estación realizó una encuesta: para cada tipo de pista se sabe cuántos esquiadores la consideran adecuada, y ese número es a_{i, j}. La lista de esquiadores se perdió. Para cada par de límites , halle cuántos esquiadores tienen exactamente esos límites, o informe que la encuesta es inconsistente, es decir, que ningún conjunto de esquiadores conduce a esos números.

Entrada

La primera línea contiene un único entero (1 \le t \le 100) — el número de casos de prueba.

La primera línea de cada caso de prueba contiene dos enteros y (1 \le n, m \le 1000) — el número de niveles de pendiente y el número de niveles de longitud.

La -ésima de las siguientes líneas contiene enteros a_{i, 1}, a_{i, 2}, \ldots, a_{i, m} (0 \le a_{i, j} \le 10^9) — las cantidades de esquiadores que consideran adecuadas las pistas con nivel de pendiente y niveles de longitud 1, 2, \ldots, m.

La suma de n \cdot m sobre todos los casos de prueba no supera 10^6.

Salida

Para cada caso de prueba, si la encuesta es inconsistente, imprima una única línea con el número .

En caso contrario, imprima líneas con números cada una: la -ésima línea debe contener c_{x, 1}, c_{x, 2}, \ldots, c_{x, m}, donde c_{x, y} es la cantidad de esquiadores con límites .

Ejemplos

Ejemplo 1

Loading
Loading

Nota

En el primer caso de prueba hay cuatro esquiadores: uno con límites , dos con límites y uno con límites . En la figura, las pistas adecuadas para cada uno de estos tipos de esquiadores están resaltadas a la izquierda, y la respuesta está a la derecha. Por ejemplo, la pista de tipo es adecuada para todos ellos, es decir, para 1 + 2 + 1 = 4 esquiadores, y la pista de tipo es adecuada solo para los dos esquiadores con límites .