Sort! Sort!! And Sort!!!

Hmm! Here you are asked to do a simple sorting. You will be given N numbers and a positive integer M. You will have to sort the N numbers in ascending order of their modulo M value. If there is a tie between an odd number and an even number (that is, their modulo M value is the same), then the odd number will precede the even number. If there is a tie between two odd numbers (that is, their modulo M value is the same), then the larger odd number will precede the smaller odd number, and if there is a tie between two even numbers (that is, their modulo M value is the same), then the smaller even number will precede the larger even number. For the remainder value of negative numbers, follow the rule of C programming language: a negative number can never have a modulus greater than zero (in case of a positive divisor). E.g., –100 MOD 3 = –1, –100 MOD 4 = 0, etc.

Input Specification

The input contains at most 20 test cases. Each test case starts with two integers N (0 < N ≤ 10000) and M (0 < M ≤ 10000). N denotes how many numbers are within this test case. Each of the next N lines contains one number. These numbers should all fit in a 32-bit signed integer. The input is terminated by a line containing two zeroes.

Output Specification

For each test case, produce a block of N + 1 lines of output. The first line of each block should contain the value of N and M. The next N lines should contain the N numbers given in the input, sorted according to the rules mentioned above. Print the last two zeroes of the input also at the end of the output.

Sample Input

1. 15 3
2. 1
3. 2
4. 3
5. 4
6. 5
7. 6
8. 7
9. 8
10. 9
11. 10
12. 11
13. 12
14. 13
15. 14
16. 15
17. 0 0

download as text file

Output for Sample Input

1. 15 3
2. 15
3. 9
4. 3
5. 6
6. 12
7. 13
8. 7
9. 1
10. 4
11. 10
12. 11
13. 5
14. 2
15. 8
16. 14
17. 0 0

download as text file