A Grouping Problem
You are given a set of N integers. You can take K different elements from them to make a group. Two groups will be different if there is at least one element which is not common to both. For example, if there are 4 elements a, b, c, d and you are asked to take two elements then ab, ad, bc, cd are all valid and different groups. A grouping system is complete if for a particular K, number of different groups is the maximum. In the former case, {ab, bc, cd, bd, ad, ac} is a complete grouping system.
For a particular complete grouping system, the fitness is calculated in the following way
- Each group of a grouping system contributes a part the multiplication of all numbers of that
group
- Contribution from all groups are added
- The fitness is equivalent to Total Contribution mod M, M is the bounding parameter
In our example, for K = 2, the fitness is F2 = (ab+bc+cd+bd+ad+ac) mod M. If K = 1, then fitnessisF1 =(a+b+c+d)modM.
Here, in this problem you have to find the complete grouping system with maximum fitness.
Input
Each test case starts with two positive integer N (2 ≤ N ≤ 1000) and M (1 ≤ M < 231). In next few lines there will be N positive integers. Each integer will be at best 1000. Input will be terminated by a case where N = M = 0.
Output
For each test case, print in a line the maximum fitness possible for a grouping system.
Sample Input
4 10 1234 4 100 1234 46 1234 00
Sample Output
5 50 5