djangg7 and ibasic are miners digging for gems in a mine. The mine has levels from underground level $1$ to level $R$. Here, $R$ is an even number.

Each level of the mine contains $K$ gems. The value of the $j$-th gem at underground level $i$ is $s_{i, j}$.

For efficiency, the two miners visit the levels in order from level $1$ to level $R$. djangg7 mines a gem at level $1$, and thereafter, the miner who did not mine a gem at the previous level mines a gem at the current level.

For fast and accurate work, exactly one gem must be mined at each level. However, if the $j$-th gem is mined at level $i$, the $j$-th gem at level $i+1$ is damaged, and its value becomes $0$. When a gem is mined at level $R$, no gems are damaged because there is no level $R+1$.

Bored, djangg7 and ibasic decided to play a game where they compare the sum of the values of the gems they each mined, and the miner with the higher sum wins. If the sums of the values of the gems mined by the two miners are equal, ibasic wins.

Thinking it best to maximize the gap, the two miners decided to use a strategy that maximizes the value obtained by subtracting the opponent's total gem value from their own total gem value after all gems have been mined. Determine who wins and the difference between the sums of the values of the gems mined by the two miners.

Input

The first line contains the number of levels $R$ and the number of gems per level $K$, separated by a space. $(1 \le R, K \le 2\,000;$ $R$ is an even number$)$

From the second line, $R$ lines follow, each containing $K$ integers representing the values of the gems at each level, separated by spaces. The $(i+1)$-th line contains the values of the gems at level $i$, $s_{i, 1}, s_{i, 2}, \ldots, s_{i, K}$, separated by spaces. $(-10^9 \le s_{i,j} \le 10^9)$

Output

On the first line, output the winner of the game and the difference between the sums of the values of the gems mined by the two miners, separated by a space.

Examples

Input 1

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

Output 1

ibasic 1

Input 2

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

Output 2

djangg7 10