1-й квалификационный раунд завершен

Задания

Показывать по одной задаче на странице / все задачи на одной странице

"B" Раскраска стены
Ограничение по времени 2 секунды
Ограничение по памяти 256 мегабайт

Девочка Маша смотрит на стену в своей комнате. Стена выложена квадратной плиткой, но вместо некоторых плиток установлены лампы. Таким образом, можно представить, что стена представляет собой клетчатый прямоугольник размером n × m, в некоторых клетках которого находятся лампы.

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

Маша просит вас придумать, как ей покрасить стену.

Формат входных данных

Входные данные содержат несколько тестовых наборов. В первой строке задано количество тестов t.

Каждый из тестов описывается следующим образом: в первой строке описания теста содержатся три числа n, m, k (1 ≤ n, m ≤ 100, 1 ≤ k ≤ max(n, m)) — размеры стены и количество различных красок у Маши.

В следующих n строках содержатся по m чисел aij:

  • aij = 0, если на позиции (i, j) находится лампа;
  • aij = 1, если на позиции (i, j) находится плитка.

Суммарное количество плиток и ламп по всем тестам не превосходит 105.

Формат выходных данных

Для каждого теста в отдельной строке сначала выведите ответ на него:

  • NO, если не существует ни одного способа покрасить стену так, как хочет Маша.
  • YES, если способ перекрасить есть. В этом случае в следующих n строках выведите по m чисел bij — цвет плитки на позиции (i, j) или 0, если на этой позиции лампа. Если подходящих раскрасок несколько, выведите любую из них.

Примеры
Входные данные
2
4 3 2
0 1 0
1 0 1
1 0 1
0 1 0
3 4 2
0 1 0 1
1 0 1 1
1 1 1 0
Выходные данные
YES
0 2 0 
2 0 2 
1 0 1 
0 1 0 
NO
 

Отправить решение

Загрузить Максимальный размер - 256 Кб

Вход

ВКонтакте Facebook It.Mail

Забыли пароль?

Регистрация

На вашу электронную почту была
отправлена инструкция по восстановлению пароля.