Bobo has generated a list of sequences:



where A+B means the concatenation of two sequences A and B.

For a given sequence , let f(i) be the Hamming distance between and (. :Bobo would like to find the minimum value of f(i) and the sum of f(i) modulo .

Note that the Hamming distance between two sequences of equal length is the number of positions at which the corresponding elements are different.

The input consists of several test cases terminated by end-of-file.

The first line contains two integers n and m.

The second line contains n integers .

* 
* 
* 
* The sum of n does not exceed .

For each test case, output two integers denoting the minimum value of f(i) and the sum of f(i) modulo .

3 3
1 2 3
3 3
1 1 1
3 3
1 2 1

1 9
1 7
0 7