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

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

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

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

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

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

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

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

Следующие $m$ строк содержат пару целых чисел $a_i, b_i$ ($1 \le a_i, b_i \le n, a_i \neq 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$), идентификатор запуска, соответствующий каждому из заданий в лог-файле. В частности, $r_i$ должен быть идентификатором запуска, соответствующим $i$-му заданию, как оно представлено в лог-файле.

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

Примеры

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

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

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

1 2 2 1 2 1 3 3 3