Description

Dingding has recently become obsessed with a number game. The game looks simple, but after many days of study he realized that winning under the simple rules is not easy. The game is as follows: in front of you is a circle of integers (a total of $n$), and you must split them, in order, into $m$ consecutive parts. Within each part, sum the numbers; take each of the $m$ sums modulo $10$, then multiply these $m$ results to obtain a number $k$. The goal is to make $k$ as large as possible or as small as possible.

For example, for the following circle of numbers ($n=4$, $m=2$):

For the minimum, $((2-1)\bmod10)\times ((4+3)\bmod10)=1\times 7=7$. For the maximum, $((2+4+3)\bmod10)\times (-1\bmod10)=9\times 9=81$. Note in particular that, whether a number is negative or positive, the result of taking modulo $10$ is always non-negative.

Please write a program to help Dingding win this game.

Input Format

The first line contains two integers, $n$ ($1\le n\le 50$) and $m$ ($1\le m\le 9$). Each of the next $n$ lines contains one integer with absolute value $\le 10^4$, given in order around the circle, with the ends connected.

Output Format

Output $2$ lines, each containing $1$ non-negative integer. The first line is the minimum value your program obtains, and the second line is the maximum value.

4 2
4
3
-1
2

7
81

Hint

Problem Source: NOIP 2003 Junior, Problem 2.

Translated by ChatGPT 5