djangg7 i ibasic to górnicy wydobywający klejnoty w kopalni. Kopalnia składa się z poziomów od $1$ do $R$ pod ziemią, gdzie $R$ jest liczbą parzystą.

Na każdym poziomie kopalni znajduje się $K$ klejnotów. Wartość $j$-tego klejnotu na poziomie $i$ wynosi $s_{i, j}$.

Dla zwiększenia wydajności pracy, obaj górnicy odwiedzają poziomy od $1$ do $R$ w kolejności. Na poziomie $1$ klejnot wydobywa djangg7, a następnie na każdym kolejnym poziomie klejnot wydobywa ten górnik, który nie wydobywał go na poziomie poprzednim.

Aby praca była szybka i dokładna, na każdym poziomie należy wydobyć dokładnie jeden klejnot. Jednak wydobycie $j$-tego klejnotu na poziomie $i$ powoduje zniszczenie $j$-tego klejnotu na poziomie $i+1$, przez co jego wartość staje się równa $0$. Podczas wydobycia na poziomie $R$ żaden klejnot nie ulega zniszczeniu, ponieważ nie istnieje poziom $R+1$.

Znudzeni djangg7 i ibasic postanowili zagrać w grę, w której porównują sumy wartości wydobytych przez siebie klejnotów; wygrywa ten, którego suma jest większa. W przypadku, gdy sumy wartości wydobytych klejnotów są równe, wygrywa ibasic.

Uznając, że najlepiej jest zmaksymalizować różnicę, obaj górnicy przyjęli strategię maksymalizacji wartości (suma wartości klejnotów własnych) minus (suma wartości klejnotów przeciwnika) po wydobyciu wszystkich klejnotów. Wyznacz zwycięzcę oraz różnicę między sumami wartości klejnotów wydobytych przez obu górników.

Wejście

W pierwszej linii podano liczbę poziomów kopalni $R$ oraz liczbę klejnotów na każdym poziomie $K$, oddzielone spacją. $(1 \le R, K \le 2\,000;$ $R$ jest liczbą parzystą$)$.

Od drugiej linii, przez $R$ linii, podano $K$ liczb całkowitych reprezentujących wartości klejnotów na każdym poziomie, oddzielone spacjami. W $(i+1)$-szej linii podano wartości klejnotów na poziomie $i$: $s_{i, 1}, s_{i, 2}, \ldots, s_{i, K}$. $(-10^9 \le s_{i,j} \le 10^9)$.

Wyjście

W pierwszej linii wypisz zwycięzcę gry oraz różnicę między sumami wartości klejnotów wydobytych przez obu górników, oddzielone spacją.

Przykład

Wejście 1

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

Wyjście 1

ibasic 1

Wejście 2

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

Wyjście 2

djangg7 10