On nous donne une suite de nombres et un entier naturel $K$.
Dans la suite, nous cherchons le plus grand nombre aux positions divisibles par $K$, où les positions des nombres dans la suite sont comptées à partir de zéro. En d'autres termes, nous cherchons le plus grand nombre aux positions $0, K, 2K, 3K, \dots$. S'il y a plusieurs occurrences du plus grand nombre parmi ceux-ci, nous choisissons la première. Nous supprimons le nombre trouvé de la suite, ce qui entraîne le décalage naturel des nombres suivants d'une position vers la gauche, c'est-à-dire qu'ils changent de position pour combler le « trou » créé.
Nous répétons l'étape décrite tant qu'il reste des nombres dans la suite. Écrivez un programme qui effectue cette tâche à notre place.
Entrée
La première ligne contient les entiers naturels $N$ et $K$ ($2 \le K \le N \le 100\,000$).
La ligne suivante contient $N$ entiers naturels avec des valeurs dans l'intervalle $[1, N]$ qui constituent la suite donnée, de la position zéro à la position $(N - 1)$.
Sortie
Affichez $N$ entiers naturels, où le $i$-ième nombre affiché est égal au nombre supprimé lors de la $i$-ième étape.
Sous-tâches
| sous-tâche | nombre de points | contraintes supplémentaires |
|---|---|---|
| 1 | 7 | $N \le 1000$ |
| 2 | 25 | $K = 2$ |
| 3 | 23 | $K \le 10$ |
| 4 | 25 | $100 \le K \le N$ |
| 5 | 20 | sans contraintes supplémentaires |
Exemples
Entrée 1
10 2 2 3 1 9 10 4 5 6 1 5
Sortie 1
10 6 4 5 2 9 3 5 1 1
Entrée 2
10 3 2 3 1 9 10 4 5 6 1 5
Sortie 2
9 10 4 5 6 2 5 3 1 1