В мире есть \(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\).
ГФО нужно найти какие игры и на каких стадионах нужно сыграть, чтобы они заработали как можно больше денег, но при этом не нарушая правила, которые они установили.
К сожалению, эта задача слишком сложная для ГФО. Поэтому они просят вас решить эту задачу.
Выходные данные
Для каждой игры в том же порядке выведите \(t_i\) (\(1 \leq t_i \leq k\)) — номер стадиона, на котором команды \(a_i\) и \(b_i\) сыграют игру. Если \(i\)-я игра не должна быть сыграна, то \(t_i\) должен быть равен \(0\).
Если существует несколько решений, выведите любое из них.
Примечание
Один из возможных решений примера показан ниже:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|