## Algorithm

Problem Name: beecrowd | 1252

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 remainder value of negative numbers follow the rule of C programming language: A negative number can never have modulus greater than zero. E.g. -100 MOD 3 = -1, -100 MOD 4 = 0 etc.

## Input

The input file contains many sets of inputs. Each set starts with two integers N (0 < N ≤ 10000) and M (0 < M ≤ 10000) which denotes how many numbers are within this set. Each of the next N lines contains one number each. These numbers should all fit in 32-bit signed integer. Input is terminated by a line containing two zeroes.

## Output

The first line of each set contains the value of N and M. The next N lines contain N numbers, sorted according to the rules mentioned above. Print the last two zeroes of the input file in the output file also.

 Sample Input Sample Output 15 3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 3 3 9 12 10 0 0 15 3 15 9 3 6 12 13 7 1 4 10 11 5 2 8 14 3 3 9 12 10 0 0

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <iostream<
#include <algorithm>

using namespace std;

int M;

bool comp (int a, int b){
if (b%M == a%M){ /// retorna primeiro os impares e depois os pares;
if(abs(a)%2 ==abs(b)%2){ ///comparando dois pares ou dois impares
if (a%2 != 0){ ///impares
return a > b;
}else{ ///a e b s?o pares
return b > a;
}
}
return abs(a)%2 > abs(b)%2; /// impares antes dos pares
}
return a%M < b%M;
}

int main()
{
int N, cont;

scanf("%d", &N);
scanf("%d", &M);

while(N!=0 && M!=0)
{
int vetor[N];
printf("%d %dn", N, M);

for(cont=0;cont < N;cont++){
scanf("%d", &vetor[cont]);
}

sort(vetor,vetor+N,comp);

for(cont=0;cont < N;cont++){
printf("%dn", vetor[cont]);
}

scanf("%d", &N);
scanf("%d", &M);

}
printf("0 0n">;

return 0;
}
``````
Copy The Code &

Input

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

Output

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

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include<bits/stdc++.h>
using namespace std;
int m;
bool comp (int a, int b){
if (b%m == a%m)
if(abs(a)%2 ==abs(b)%2){
if (a%2 != 0){
return a > b;
}else{
return b > a;
}
}
return abs(a)%2 > abs(b)%2;
}
return a%m < b%m;
}
int main()
{
int n;

while(cin>>n>>m&&n&&m){
int a[n];
for(int i=0;i < n;i++)
{
cin>>a[i];
}
sort(a,a+n,comp);
cout<<n<<" "<<m<<endl;
for(int i=0;i < n;i++)
cout<<a[i]<<endl;
}
printf("0 0n">;
}
``````
Copy The Code &

Input

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

Output

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