Busy Beaver crée un nouveau langage pour son cours de linguistique ! Il a déjà décidé que son langage aura un alphabet dont les lettres sont les entiers $1, \dots, NM$ dans cet ordre ; maintenant, il veut créer quelques mots pour ce langage.

Comme Busy Beaver s'intéresse aux statistiques, il veut contrôler les fréquences des lettres apparaissant dans les mots, il a donc choisi un multi-ensemble $a$ de taille $NM$ de lettres issues de son alphabet. Il va maintenant former $N$ mots de $M$ lettres chacun, de telle sorte que chaque lettre de $a$ soit utilisée exactement une fois (c'est-à-dire que si une lettre donnée $x$ apparaît exactement $k$ fois dans $a$, alors elle est utilisée exactement $k$ fois parmi l'ensemble des $N$ mots).

Après avoir formé les mots, Busy Beaver prévoit de les organiser dans un dictionnaire, il va donc trier lexicographiquement ses $N$ mots pour produire la séquence de mots $s_1, \dots, s_N$. Busy Beaver aime que les chaînes soient lexicographiquement petites, donc pour chaque $k$ de $1$ à $N$, il veut connaître la valeur lexicographiquement minimale possible de $s_k$ parmi tous les choix de mots.

Remarque : la réponse pour chaque $s_k$ est indépendante ; par exemple, le choix des mots permettant de minimiser $s_1$ peut être différent du choix des mots permettant de minimiser $s_2$.

Entrée

La première ligne contient deux entiers positifs $N, M$ ($1 \le NM \le 10^6$). La deuxième ligne contient $NM$ entiers $a_1, \dots, a_{NM}$ composant le multi-ensemble $a$ ($1 \le a_j \le NM$).

Sortie

Pour chaque $k$ de $1$ à $N$, affichez la valeur minimale possible de $s_k$ sur sa propre ligne sous la forme d'une séquence d'entiers séparés par des espaces.

Exemples

Exemples 1

4 3
1 1 2 2 3 3 4 4 5 5 6 6

1 1 2
1 2 3
2 2 3
2 3 4

Exemples 2

3 4
12 4 4 4 1 1 4 4 6 4 1 4

1 1 1 4
1 4 4 4
1 4 4 12

Exemples 3

4 5
12 7 17 3 6 11 9 2 17 7 1 6 9 12 6 3 9 12 2 15

1 2 2 3 3
2 2 3 3 6
2 3 6 7 7
3 3 6 6 6

Exemples 4

1 1
1

1

Remarque

Dans le premier exemple, les choix de mots suivants minimisent chaque $s_k$ :

En choisissant les mots 112, 233, 445, 566, nous obtenons $s = 112, 233, 445, 566$, donc $s_1 = 112$ comme souhaité. En choisissant les mots 123, 456, 123, 456, nous obtenons $s = 123, 123, 456, 456$, donc $s_2 = 123$ comme souhaité. En choisissant les mots 166, 155, 344, 223, nous obtenons $s = 155, 166, 223, 344$, donc $s_3 = 223$ comme souhaité. En choisissant les mots 234, 234, 156, 156, nous obtenons $s = 156, 156, 234, 234$, donc $s_4 = 234$ comme souhaité.

Il peut être démontré que dans tous ces cas, il n'y a aucun moyen de choisir les mots de sorte que le $s_k$ respectif soit encore plus petit lexicographiquement.