问题描述

具体描述见教材p265： 丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单，但丁丁在研究了许多天之后却发觉，原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的，在你面前有一圈整数(一共n个)，你要按顺序将其分为m个部分，各部分内的数字相加，相加所得的m个结果对10取模后再相乘，最终得到一个数k。游戏的要求是使你所得的k最大或者最小。 例如，对于下面这圈数字(n=4，m=2)(右图)：

当求最小值时，为( (2-1) mod 10) × ( (4+3) mod 10 )= 1 × 7 = 7，当求最大值时，为( (2+4+3) mod 10) × (-1 mod 10 ) = 9 × 9 = 81。特别值得注意的是，无论是负数还是正数，对 10 取模的结果均为非负值。丁丁请你编写程序帮他赢得这个游戏。

格式

输入

第1行有两个整数，n(1≤n≤50)和m(1≤m≤9)。以下n行每行有一个整数，其绝对值不大于104，按顺序给出圈中的数字，首尾相接。

输出

输出有两行，各包含一个非负整数。第 1 行是你的程序得到 的最小值，第 2 行是最大值。

样例

4 2
4 
3 
-1
2

7
81

限制

1s, 64MB.