Description

srf 和qtc 在一个规模为$1$ × $n$ 的棋盘中下棋。规则是：

第一个人可以下在第$1$ 到$m$ 中的任意一个位置。接下来每一个人可以下在第$i + 1$ 到$i + m$ 的任意一个位置，其中$i$ 为上一个人下棋的位置。

每个格子里有一个数，如果一个人下棋在格子$i$，会得到$a_i$的分值。

当不能继续操作时，结束。

小srf 请你帮他算一下，当他和qtc 都采取最优策略时，他的得分减去qtc 的得分。

Input Format

第一行：两个正整数$n$ 和$m$,用空格隔开。

第二行：$n$ 个数，表示棋盘上的数字。

Output Format

两行，每行各一个数， 第一个数为srf 先手时的答案， 第二个数为qtc 先手时的答案。

Sample

样例输入1

1 1
1

样例输出1

1
-1

样例输入2

2 2
2 2

样例输出2

2
-2

Hint

对于30%的数据，$n ≤ 15$；

对于60%的数据，$m ≤ 100$；

对于100%的数据，$1 ≤ n ≤ 100000$，$1 ≤ m ≤ n$，

$a$ 数组中的数保证在int (pascal 的longint) 范围内。