Le professeur Chen, éminent expert en paléographie computationnelle, a passé des années à étudier les manuscrits de la dynastie Non-Redondante. Les scribes de cette époque suivaient une doctrine esthétique particulière : ils croyaient qu'un texte perd sa puissance spirituelle s'il contient des « échos ».
Dans ce contexte, un écho anagrammatique est défini comme deux segments distincts quelconques d'un texte qui, sans être nécessairement identiques dans leur ordre, contiennent exactement les mêmes symboles dans les mêmes quantités. Pour un texte représenté sous la forme d'une séquence de symboles, un écho existe s'il y a deux positions de départ différentes $x$ et $y$ telles que le sous-tableau de longueur $l$ commençant en $x$ soit une permutation du sous-tableau de longueur $l$ commençant en $y$. Par exemple, considérons la séquence $[1, 2, 1, 1, 3, 1, 2, 1]$. Le segment de longueur $4$ commençant à la deuxième position, $[2, 1, 1, 3]$, et le segment de longueur $4$ commençant à la cinquième position, $[3, 1, 2, 1]$, forment un écho anagrammatique.
Le professeur Chen a mis au jour plusieurs de ces parchemins, mais de nombreux symboles se sont effacés avec le temps, laissant des lacunes (représentées par $0$). Votre tâche consiste à combler ces lacunes à l'aide de symboles issus de l'ensemble autorisé $\{1, 2, \dots, k\}$ de sorte que le Score de Dissonance (Dissonance Score) du parchemin obtenu soit minimisé. Le Score de Dissonance est la longueur maximale $l$ d'un écho anagrammatique présent dans la séquence complétée.
Entrée
Il y a plusieurs cas de test. La première ligne de l'entrée contient un entier $T$ ($1 \le T \le 10^4$) indiquant le nombre de cas de test. Pour chaque cas de test :
La première ligne contient deux entiers $n$ et $k$ ($2 \le n \le 2 \times 10^5$, $1 \le k \le n$).
La deuxième ligne contient $n$ entiers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le k$).
Il est garanti que la somme des $n$ sur l'ensemble des cas de test ne dépasse pas $2 \times 10^5$.
Sortie
Pour chaque cas de test, affichez $n$ entiers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le k$) représentant la séquence restaurée. La séquence $b$ doit correspondre à $a$ à toutes les positions où $a_i \neq 0$, et elle doit atteindre le Score de Dissonance minimal possible.
S'il existe plusieurs façons de restaurer le parchemin de manière optimale, le professeur Chen acceptera n'importe laquelle d'entre elles.
Exemple
Entrée
4 8 3 0 1 0 2 1 3 0 2 3 3 1 0 2 9 7 0 1 1 0 5 0 4 0 7 6 6 0 0 0 0 0 0
Sortie
1 1 3 2 1 3 2 2 1 3 2 2 1 1 3 5 6 4 4 7 1 2 3 4 5 6