En tant qu'apprenti passionné d'algorithmes, il n'est pas surprenant que Mike ait du mal à gérer des systèmes trop complexes. Malheureusement, cela s'est avéré être un problème majeur dans l'entreprise où il effectue actuellement son stage.

Le projet assigné à Mike consiste à travailler sur le « Intelligent Cluster for Parallel Computation » de l'entreprise. C'est juste un nom sophistiqué ; en réalité, le système est un simple ordonnanceur de tâches, gérant un total de $n$ tâches. Certaines tâches peuvent dépendre de l'exécution réussie d'autres tâches avant de pouvoir être exécutées. Il y a un total de $m$ dépendances de ce type.

Il est garanti qu'il n'y a aucune dépendance circulaire (directe ou indirecte) entre les tâches.

Lorsqu'une exécution est lancée, le système choisit intelligemment un ordre pour exécuter ces tâches de sorte que toutes les dépendances soient respectées (l'ordre peut changer entre différentes exécutions). Après avoir choisi un ordre valide, il commence à exécuter chacune des $n$ tâches dans cet ordre. Lorsque le système commence à exécuter une tâche, il écrit l'identifiant de la tâche dans un fichier journal.

Malheureusement, aujourd'hui était le premier jour de stage de Mike dans l'entreprise et il n'a pas été très prudent. Par conséquent, il a accidentellement lancé le système $k$ fois en parallèle. Le système a commencé à lancer les tâches de manière erratique et à écrire dans le fichier journal. Désormais, le fichier journal contient $n \cdot k$ identifiants de toutes les tâches qui ont été exécutées. Les identifiants des tâches d'une même exécution ont été imprimés dans l'ordre où elles ont été exécutées, mais les sorties des différentes exécutions peuvent apparaître entremêlées de manière arbitraire.

Votre tâche consiste à déterminer quelles tâches ont été exécutées dans chacune des $k$ exécutions à partir des informations contenues dans le fichier journal.

Entrée

La première ligne de l'entrée contient trois entiers $n, k, m$ ($1 \le n, k \le 500\,000$, $0 \le m \le 250\,000$, $n \cdot k \le 500\,000$), le nombre de tâches dans le système, le nombre d'exécutions que Mike a déclenchées, et le nombre de dépendances.

Les $m$ lignes suivantes contiennent une paire $a_i, b_i$ ($1 \le a_i, b_i \le n$, $a_i \neq b_i$, pour tout $1 \le i \le m$) décrivant une dépendance du type : « la tâche $a_i$ doit être exécutée avant la tâche $b_i$ ».

Enfin, la dernière ligne de l'entrée contient $n \cdot k$ entiers $c_i$ ($1 \le c_i \le n$, pour tout $1 \le i \le n \cdot k$), les identifiants des tâches qui ont été écrits dans le fichier journal, dans l'ordre.

Sortie

Affichez une seule ligne composée de $n \cdot k$ entiers $r_i$ ($1 \le r_i \le k$, pour tout $1 \le i \le n \cdot k$), l'identifiant de l'exécution correspondant à chacune des tâches dans le fichier journal. Plus précisément, $r_i$ doit être l'identifiant de l'exécution correspondant à la $i$-ème tâche, telle qu'elle apparaît dans le fichier journal.

Si plusieurs solutions sont possibles, n'importe laquelle est acceptée. Il est garanti que les données d'entrée sont valides et qu'une solution existe toujours.

Exemples

Entrée 1

3 3 2
1 2
1 3
1 1 2 3 3 2 1 2 3

Sortie 1

1 2 2 1 2 1 3 3 3