F. Футбол
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В мире есть $$$n$$$ футбольных команд.

Главная футбольная организация (ГФО) хочет провести не более $$$m$$$ игр. ГФО хочет, чтобы $$$i$$$-я игра была сыграна между командами $$$a_i$$$ и $$$b_i$$$ на одном из $$$k$$$ стадионов.

Пусть $$$s_{ij}$$$ будет количеством игр, которые сыграла $$$i$$$-я команда на $$$j$$$-м стадионе. ГФО не хочет, чтобы какая-то команда сыграла на много больше матчей на одному стадионе, чем на каком-то другом. Поэтому, для каждой команды $$$i$$$, абсолютная разница между максимом и минимум среди чисел $$$s_{i1}, s_{i2}, \ldots, s_{ik}$$$ не должна превосходить $$$2$$$.

Каждая команда имеет $$$w_i$$$ — количество денег, которые получит ГФО за каждую игру $$$i$$$-й команды. Если $$$i$$$-я команда сыграет $$$l$$$ матчей, то ГФО заработает $$$w_i \cdot l$$$.

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

К сожалению, эта задача слишком сложная для ГФО. Поэтому они просят вас решить эту задачу.

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

Первая строка содержит три целых числа $$$n$$$, $$$m$$$, $$$k$$$ ($$$3 \leq n \leq 100$$$, $$$0 \leq m \leq 1\,000$$$, $$$1 \leq k \leq 1\,000$$$) — количество команд, количество игр и количество стадионов.

Вторая строка содержит $$$n$$$ целых чисел $$$w_1, w_2, \ldots, w_n$$$ ($$$1 \leq w_i \leq 1\,000$$$) — количество денег, которое получит ГФО за каждую игру $$$i$$$-й команды.

Каждая из следующих $$$m$$$ строк содержит два целых числа $$$a_i$$$ и $$$b_i$$$ ($$$1 \leq a_i, b_i \leq n$$$, $$$a_i \neq b_i$$$) — команды, которые могут сыграть $$$i$$$-ю игру. Гарантируется, что каждая пара команд может сыграть не более одной игры.

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

Для каждой игры в том же порядке выведите $$$t_i$$$ ($$$1 \leq t_i \leq k$$$) — номер стадиона, на котором команды $$$a_i$$$ и $$$b_i$$$ сыграют игру. Если $$$i$$$-я игра не должна быть сыграна, то $$$t_i$$$ должен быть равен $$$0$$$.

Если существует несколько решений, выведите любое из них.

Пример
Входные данные
7 11 3
4 7 8 10 10 9 3
6 2
6 1
7 6
4 3
4 6
3 1
5 3
7 5
7 3
4 2
1 4
Выходные данные
3
2
1
1
3
1
2
1
2
3
2
Примечание

Один из возможных решений примера показан ниже: