Ошибка

Как ученик-энтузиаст алгоритмов, неудивительно, что Майк изо всех сил пытается справиться с чрезмерно сложными системами. К сожалению, это оказалось большой проблемой в компании, которую он сейчас стажирует.

Назначенный Майком проект включает в себя работу с интеллектуальным кластером компании для параллельных вычислений. Это просто причудливое имя; на самом деле система представляет собой простой планировщик заданий, обрабатывающий в общей сложности $n$ заданий. Некоторые задания могут зависеть от успешного выполнения других заданий, прежде чем их можно будет выполнить. Всего таких зависимостей $m$.

Гарантируется отсутствие (прямых или косвенных) циклических зависимостей между заданиями.

Когда стартует запуск, системы интеллектуально выбирают порядок выполнения этих заданий, чтобы соблюдались все зависимости (порядок может меняться между разными запусками). После выбора действительного порядка он начинает выполнять каждое из $n$ заданий в этом порядке. Когда система начинает выполнение задания, она выводит $id$ задания в файл журнала.

К сожалению, сегодня был первый день стажировки Майка в компании, и он не проявил особой осторожности. Как следствие, он случайно запустил систему $k$ раз параллельно. Система начала беспорядочно запускать задания и печатать в файл журнала. Теперь файл журнала содержит $n\cdot k$ идентификаторов всех выполненных заданий. Идентификаторы заданий из одного и того же прогона были напечатаны в том порядке, в котором они были выполнены, но выходные данные из разных прогонов могут оказаться произвольно переплетенными.

Ваша задача — выяснить, какие задания были выполнены в каждом из $k$ запусков, на основе информации внутри файла журнала.

Входные данные

Первая строка содержит три целых числа $n,k,m(1\le n,k\le 500000,0\le m\le 250000,n\cdot k\le 500000)$ — количество заданий в системе, количество запусков Майка и количество зависимостей.

Каждая из следующих $m$ строк содержит пару $a_i,b_i(1\le a_i,b_i\le n,a_i\ne b_i$, для всех $1\le i\le m)$ описывая зависимость вида: “работа $a_i$ должна быть выполнена перед работой $b_i$”.

Последняя строка содержит $n\cdot k$ целых чисел $c_i(1\le c_i\le n$, для всех $1\le i\le n\cdot k)$ — идентификационные номера заданий, выведенные в файл.

Выходные данные

Выведите одну строку, состоящую из $n\cdot k$ целых чисел $r_i(1\le r_i\le k$, для всех $1\le i\le n\cdot k)$, $id$ запуска соответствует каждому заданию в файле журнала. В частности, $r_i$ должен быть $id$ запуска, соответствующего $i$-му заданию, как он отображается в файле журнала.

Если существует несколько решений, выведите любое. Гарантируется, что входные данные непротиворечивы и решение всегда существует.

Примеры