djangg7 и ibasic — шахтеры, добывающие драгоценные камни в шахте. Шахта состоит из уровней с подземного $1$-го по $R$-й, где $R$ — четное число.
На каждом уровне шахты находится $K$ драгоценных камней. Ценность $j$-го камня на $i$-м подземном уровне равна $s_{i, j}$.
Для повышения эффективности работы они посещают уровни по очереди, начиная с $1$-го и заканчивая $R$-м. На $1$-м уровне камень добывает djangg7, а далее на каждом следующем уровне камень добывает тот шахтер, который не работал на предыдущем уровне.
Для быстроты и точности работы на каждом уровне необходимо добыть ровно один камень. Однако, если на $i$-м уровне добыть $j$-й камень, то $j$-й камень на $(i+1)$-м уровне будет поврежден, и его ценность станет равной $0$. При добыче камня на $R$-м уровне никакие камни не повреждаются, так как $(R+1)$-го уровня не существует.
Заскучав, djangg7 и ibasic решили сыграть в игру: они сравнивают сумму ценностей добытых ими камней, и побеждает тот, у кого эта сумма больше. Если суммы ценностей равны, побеждает ibasic.
Считая, что лучше всего максимально увеличить разрыв, оба шахтера решили придерживаться стратегии, при которой каждый из них максимизирует разность между суммой ценностей своих камней и суммой ценностей камней соперника. Определите, кто победит в игре, и найдите разность между суммами ценностей добытых ими камней.
Входные данные
В первой строке через пробел заданы количество уровней шахты $R$ и количество камней на каждом уровне $K$ $(1 \le R, K \le 2\,000; R$ — четное число$)$.
Начиная со второй строки, следуют $R$ строк, каждая из которых содержит $K$ целых чисел, представляющих ценность камней на соответствующем уровне. В $(i+1)$-й строке через пробел заданы ценности камней $s_{i, 1}, s_{i, 2}, \ldots, s_{i, K}$ на $i$-м подземном уровне $(-10^9 \le s_{i,j} \le 10^9)$.
Выходные данные
В первой строке выведите имя победителя и разность между суммой ценностей камней, добытых победителем, и суммой ценностей камней, добытых проигравшим, разделив их пробелом.
Примеры
Пример 1
4 4 1 2 2 2 5 5 4 0 5 1 5 2 3 0 4 3
Выходные данные 1
ibasic 1
Пример 2
2 5 8 4 7 9 10 -5 -9 -4 -7 -6
Выходные данные 2
djangg7 10