Помилка

Як учень-ентузіаст алгоритмів, Майк не дивно, що зіштовхується з труднощами при роботі з надмірно складними системами. На жаль, це стало великою проблемою в компанії, де він зараз проходить стажування.

Проєкт, на якому працює Майк, передбачає взаємодію з інтелектуальним кластером компанії для паралельних обчислень. Це просто вигадлива назва; насправді система є простим планувальником завдань, що обробляє загалом $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$-му завданню, як він відображається у файлі журналу.

Якщо існує кілька рішень, виведіть будь-яке. Гарантується, що вхідні дані не суперечливі і рішення завжди існує.

Приклади