题目描述

Gakkipan有一个手环，手环由n个珠子构成，每个珠子上有一个值，Gakkipan想把这个手环拆成m段，每一段的价值为所有珠子值的和对10取模，如果为负数，再加上10。最后的需要你求出m段价值乘积的最小值和最大值。

例如，下面这个手环（$n=4，m=2$）：

最小值为$((2-1) \mod 10) \times ((4+3) \mod 10)=1×7=7$ 最大值为$((2+4+3) \mod 10) \times (-1 \mod 10)=9×9=81$。

输入

输入第一行有两个整数，$n（1≤n≤50）$和$m（1≤m≤9）$。以下$n$行每行有个整数，其绝对值不大于$10^4$，按顺序给出手环上每个珠子的值，首尾相连。

输出

输出有两行，各包含一个非负整数。第一行是最小值，第二行是最大值。

样例输入

4 2
4
3
-1
2

样例输出

7
81