Como aprendiz entusiasta de los algoritmos, no es una gran sorpresa que Mike tenga dificultades para lidiar con sistemas excesivamente complejos. Desafortunadamente, esto resultó ser un gran problema en la empresa donde actualmente realiza sus prácticas.
El proyecto asignado a Mike consiste en trabajar con el Clúster Inteligente para Computación Paralela de la empresa. Este es solo un nombre elegante; en realidad, el sistema es simplemente un programador de tareas sencillo que maneja un total de $n$ tareas. Algunas tareas pueden depender de la ejecución exitosa de otras tareas antes de poder ser ejecutadas. Hay un total de $m$ dependencias de este tipo.
Se garantiza que no existen dependencias circulares (directas o indirectas) entre las tareas.
Cuando se inicia una ejecución, el sistema elige inteligentemente un orden para ejecutar estas tareas de modo que se cumplan todas las dependencias (el orden puede cambiar entre diferentes ejecuciones). Después de elegir un orden válido, comienza a ejecutar cada una de las $n$ tareas en ese orden. Cuando el sistema comienza a ejecutar una tarea, imprime el identificador de la tarea en un archivo de registro (log).
Desafortunadamente, hoy fue el primer día de Mike como pasante en la empresa y no fue muy precavido. Como consecuencia, ejecutó accidentalmente el sistema $k$ veces en paralelo. El sistema comenzó a lanzar tareas de forma errática e imprimiendo en el archivo de registro. Ahora, el archivo de registro contiene $n \cdot k$ identificadores de todas las tareas que fueron ejecutadas. Los identificadores de las tareas de una misma ejecución se han impreso en el orden en que fueron ejecutadas, pero las salidas de diferentes ejecuciones pueden aparecer entrelazadas arbitrariamente.
Tu tarea es determinar qué tareas fueron ejecutadas en cada una de las $k$ ejecuciones a partir de la información contenida en el archivo de registro.
Entrada
La primera línea de la entrada contendrá tres enteros $n, k, m$ ($1 \le n, k \le 500\,000$, $0 \le m \le 250\,000$, $n \cdot k \le 500\,000$), el número de tareas en el sistema, el número de ejecuciones que Mike activó y el número de dependencias.
Las siguientes $m$ líneas contendrán un par $a_i, b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$, para todo $1 \le i \le m$) describiendo una dependencia del tipo: "la tarea $a_i$ debe ejecutarse antes que la tarea $b_i$".
Finalmente, la última línea de la entrada contiene $n \cdot k$ enteros $c_i$ ($1 \le c_i \le n$, para todo $1 \le i \le n \cdot k$), los identificadores de las tareas que se han impreso en el archivo de registro, en orden.
Salida
Imprime una única línea que consista en $n \cdot k$ enteros $r_i$ ($1 \le r_i \le k$, para todo $1 \le i \le n \cdot k$), el identificador de la ejecución correspondiente a cada una de las tareas en el archivo de registro. Más específicamente, $r_i$ debe ser el identificador de la ejecución correspondiente a la $i$-ésima tarea, tal como aparece en el archivo de registro.
Si existen múltiples soluciones, cualquiera de ellas es aceptada. Se garantiza que los datos de entrada son válidos y que siempre existe una solución.
Ejemplos
Entrada 1
3 3 2 1 2 1 3 1 1 2 3 3 2 1 2 3
Salida 1
1 2 2 1 2 1 3 3 3