Description

srf 和 qtc 在一个规模为 1 × n 的棋盘中下棋。规则是：
第一个人可以下在第 1 到 m 中的任意一个位置。接下来每一个人可以下在第 i + 1 到
i + m 的任意一个位置，其中 i 为上一个人下棋的位置。
每个格子里有一个数，如果一个人下棋在格子 i，会得到 a[i]的分值。
当不能继续操作时，结束。
小 srf 请你帮他算一下，当他和 qtc 都采取最优策略时，他的得分减去 qtc 的得分。

Format

Input

第一行：两个正整数 n 和 m,用空格隔开。
第二行：n 个数，表示棋盘上的数字

Output

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

Sample 1

Input

1 1
1

Output

1
-1

Sample 2

Input

2 2 
2 2

Output

2
-2

Limitation

对于 30%的数据，n ≤ 15；
对于 60%的数据，m ≤ 100；
对于 100%的数据，1 ≤ n ≤ 100000，1 ≤ m ≤ n，
a 数组中的数保证在 int (pascal 的 longint) 范围内。