Sorting by remainder

You are given $n$ integers and a number $M$. Sort the numbers by these rules:

1. First by increasing remainder $a \bmod M$. The remainder keeps the sign of the number (like % in C++): for example, $-7 \bmod 3 = -1$, $7 \bmod 3 = 1$.
2. If the remainders are equal, an odd number comes before an even one.
3. If both are odd, the larger comes first; if both are even, the smaller comes first.

The first line contains $n$ and $M$ ($1 \le n \le 10^5$, $1 \le M \le 10^4$). The second line contains $n$ integers ($|a_i| \le 10^9$).

A single line with $n$ numbers — the sorted array.

The three rules form one comparator: different remainders — by remainder; different parity — odd first; otherwise odd numbers in decreasing and even numbers in increasing order. A negative number can be odd too: $-3$ is odd.

In Python -7 % 3 gives 2, which is not the remainder from the statement. Get the signed remainder with math.fmod or -(abs(a) % M). In the second example the remainders are: $-7 \to -1$, $-4 \to -1$, $-3 \to 0$, $0 \to 0$, $3 \to 0$, $4 \to 1$, $7 \to 1$; the answer is -7 -4 3 -3 0 7 4.

Source: UVa 11321.