J18 实践-8 数字游戏

题目描述

佩琦最近沉迷于一个数字游戏之中。 游戏是这样的，有一圈整数（一共 $n$ 个），需要按顺序将其分为 $m$ 个部分，各部分内的数字相加，相加所得的 $m$ 个结果对 $10$ 取模后再相乘，最终得到一个数 $k$ 。 游戏的要求是使所得的 $k$ 最大或者最小。 例如，对于下面这圈数字（ $n=4,m=2$）：

要求最小值时，$((2-1)\bmod 10)\times((4+3)\bmod 10)=1\times7=7$，要求最大值时，为 $((2+4+3) \bmod 10)\times (-1 \bmod 10)=9\times 9=81$。 无论是负数还是正数，对 $10$ 取模的结果均为非负值。 请你编写程序帮他赢得这个游戏。

输入格式

第一行有两个整数，$n$ 和 $m$ 。以下 $n$ 行，每行有一个整数，其绝对值 $\le 10^4$，按顺序给出圈中的数字，首尾相接。

输出格式

共两行，各包含一个非负整数。 第一行是程序得到的最小值，第二行是最大值。

样例输入

4 2
4
3
-1
2

样例输出

7
81

样例分析

如上所述。

数据范围

对于 $100\%$ 的数据：$1 \leq n \leq 50, 1\leq m < 9$。