Сортировка по остатку

Даны $n$ целых чисел и число $M$. Отсортируйте числа по правилам:

1. Сначала по возрастанию остатка $a \bmod M$. Остаток берётся со знаком числа (как % в C++): например, $-7 \bmod 3 = -1$, $7 \bmod 3 = 1$.
2. При равных остатках нечётное число стоит раньше чётного.
3. Если оба нечётные — раньше большее; если оба чётные — раньше меньшее.

В первой строке $n$ и $M$ ($1 \le n \le 10^5$, $1 \le M \le 10^4$). Во второй — $n$ целых чисел ($|a_i| \le 10^9$).

В одной строке $n$ чисел — отсортированный массив.

Три правила записываются одним компаратором: если остатки различны — по остатку, если различна чётность — нечётное раньше, иначе нечётные по убыванию, чётные по возрастанию. Отрицательное число тоже может быть нечётным: $-3$ нечётно.

В Python -7 % 3 даёт 2 — это не тот остаток. Остаток со знаком получите через math.fmod или -(abs(a) % M). Во втором примере остатки: $-7 \to -1$, $-4 \to -1$, $-3 \to 0$, $0 \to 0$, $3 \to 0$, $4 \to 1$, $7 \to 1$; ответ -7 -4 3 -3 0 7 4.

Источник: UVa 11321.