В исследовательском центре компании Q разработали новый многоядерный процессор. Процессор состоит из n ядер, в распоряжении которых имеется k ячеек общей кеш-памяти. Рассмотрим работу этого процессора.
Каждый такт каждому ядру процессора подается одна инструкция: либо ничего не делать, либо номер ячейки, в которую нужно записать информацию. Получив команду, ядро мгновенно выполняет ее. Иногда происходит ситуация, когда в течение одного и того же такта несколько ядер пытаются записать информацию в одну ячейку. К сожалению, разработчики не предусмотрели возможность разрешения конфликтов между ядрами, поэтому в таком случае происходит дедлок: все эти ядра и соответствующая ячейка памяти блокируются навсегда. Каждое из заблокированных ядер игнорирует все дальнейшие команды, и ни одно ядро в дальнейшем не сможет записать информацию в заблокированную ячейку. Если какое-то из ядер попытается записать информацию в заблокированную ячейку, оно немедленно блокируется.
Команда разработчиков процессора хочет досконально изучить ситуацию дедлок. Поэтому им требуется программа, которая по заданному набору инструкций для каждого ядра в течении m тактов будет моделировать работу процессора. Вам повезло, и эту интересную работу доверили вам. По заданным инструкциям в течении m тактов определите для каждого ядра номер такта, во время которого оно станет заблокированным. Считается, что изначально все ядра и все ячейки памяти не заблокированы.
Выходные данные
Выведите n строк. В i-й строке выведите целое число ti, равное 0, если i-е ядро не будет заблокировано, либо равное номеру такта, в течение которого ядро будет заблокировано.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3 5
1 0 0
1 0 2
2 3 1
3 2 0
|
1
1
3
0
|
|
2
|
3 2 2
1 2
1 2
2 2
|
1
1
0
|
|
3
|
1 1 1
0
|
0
|