djangg7 e ibasic son mineros que extraen gemas en una mina. La mina tiene niveles desde el nivel subterráneo $1$ hasta el nivel $R$. Se garantiza que $R$ es un número par.

En cada nivel de la mina hay $K$ gemas. El valor de la $j$-ésima gema en el nivel subterráneo $i$ es $s_{i, j}$.

Para mayor eficiencia, ambos visitan los niveles desde el $1$ hasta el $R$ en orden. En el nivel subterráneo $1$, djangg7 extrae una gema, y a partir de ahí, el minero que no extrajo una gema en el nivel anterior es quien extrae la gema en el nivel actual.

Para un trabajo rápido y preciso, se debe extraer exactamente una gema por nivel. Sin embargo, si se extrae la $j$-ésima gema en el nivel subterráneo $i$, la $j$-ésima gema del nivel subterráneo $i+1$ se daña, y su valor pasa a ser $0$. Al extraer una gema en el nivel subterráneo $R$, no se daña ninguna gema, ya que no existe un nivel $R+1$.

Aburridos, djangg7 e ibasic decidieron jugar un juego donde comparan la suma de los valores de las gemas que cada uno extrajo; el minero con la suma más alta gana. Si las sumas son iguales, gana ibasic.

Pensando que es mejor maximizar la diferencia, ambos mineros decidieron utilizar una estrategia para maximizar el valor resultante de restar la suma de las gemas del oponente a la suma de sus propias gemas extraídas. Determina quién gana y cuál es la diferencia entre las sumas de los valores de las gemas extraídas por ambos mineros.

Entrada

La primera línea contiene el número de niveles de la mina $R$ y el número de gemas en cada nivel $K$, separados por un espacio. $(1 \le R, K \le 2\,000;$ $R$ es par$)$

Desde la segunda línea, se proporcionan $R$ líneas, cada una con $K$ enteros separados por espacios que representan el valor de las gemas en cada nivel. La línea $i+1$ contiene los valores de las gemas en el nivel subterráneo $i$: $s_{i, 1}, s_{i, 2}, \ldots, s_{i, K}$. $(-10^9 \le s_{i,j} \le 10^9)$

Salida

En la primera línea, imprime el ganador del juego y la diferencia entre la suma de los valores de las gemas extraídas por ambos mineros, separados por un espacio.

Ejemplos

Entrada 1

4 4
1 2 2 2
5 5 4 0
5 1 5 2
3 0 4 3

Salida 1

ibasic 1

Entrada 2

2 5
8 4 7 9 10
-5 -9 -4 -7 -6

Salida 2

djangg7 10