djangg7 和 ibasic 是在矿井中挖掘宝石的矿工。矿井共有从地下 $1$ 层到地下 $R$ 层，其中 $R$ 为偶数。

矿井的每一层都有 $K$ 颗宝石。地下 $i$ 层第 $j$ 颗宝石的价值为 $s_{i, j}$。

为了提高工作效率，两人按顺序从地下 $1$ 层访问到地下 $R$ 层。在地下 $1$ 层由 djangg7 挖掘宝石，此后每一层由上一层未挖掘宝石的矿工进行挖掘。

为了保证工作既快速又准确，每一层必须且只能挖掘一颗宝石。然而，如果在地下 $i$ 层挖掘了第 $j$ 颗宝石，地下 $i+1$ 层第 $j$ 颗宝石将会受损，受损宝石的价值变为 $0$。在地下 $R$ 层挖掘宝石时，由于不存在地下 $R+1$ 层，因此不会有任何宝石受损。

感到无聊的 djangg7 和 ibasic 决定进行一场游戏：比较各自挖掘到的宝石价值总和，价值总和较高的一方获胜。如果两人挖掘的宝石价值总和相同，则 ibasic 获胜。

两位矿工认为拉大差距更好，因此他们决定采取策略，使得在挖掘完所有宝石后，自己挖掘的宝石价值总和减去对方挖掘的宝石价值总和的值最大化。请计算最终获胜者以及两人挖掘宝石价值总和的差值。

第一行包含两个由空格分隔的整数 $R$ 和 $K$，分别表示矿井的层数和每层的宝石数量。$(1 \le R, K \le 2\,000;$ $R$ 为偶数$)$

从第二行开始的 $R$ 行，每行包含 $K$ 个由空格分隔的整数，表示该层宝石的价值。第 $i+1$ 行包含地下 $i$ 层宝石的价值 $s_{i, 1}, s_{i, 2}, \ldots, s_{i, K}$。$(-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