F. Поликарп и сено
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У фермера Поликарпа есть склад с сеном, который можно представить как прямоугольную таблицу n × m, где n — количество строк, а m — количество столбцов в таблице. В каждой клетке таблицы содержится стог сена. Высота в метрах стога, расположенного в i-й строке и j-м столбце, равна целому числу ai, j и совпадает с количеством кубометров сена в данном стоге, поскольку все клетки имеют размер основания 1 × 1.

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

Поликарп хочет, чтобы после реорганизации выполнялись следующие требования:

  • суммарный объём сена на складе должен быть в точности равен k,
  • высоты всех стогов (то есть клеток, содержащих ненулевое количество сена) должны быть одинаковыми,
  • высота хотя бы одного стога должна остаться такой же, как была,
  • для устойчивости оставшейся конструкции все стога должны представлять собой одну связную область.

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

Помогите Поликарпу выполнить это нелёгкое задание или сообщите, что это невозможно.

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

В первой строке входных данных находятся три целых числа n, m (1 ≤ n, m ≤ 1000) и k (1 ≤ k ≤ 1018) — количество строк и столбцов прямоугольной таблицы, в которую уложены стога с сеном, и требуемое суммарное количество кубометров сена после реорганизации.

Далее следует n строк по m целых положительных чисел ai, j (1 ≤ ai, j ≤ 109), где ai, j равно количеству кубометров сена, из которых состоит стог, который находится в i-й строке и j-м столбце таблицы.

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

В первой строке выведите «YES», если Поликарп сможет совершить реорганизацию, и «NO» в противном случае. Если ответ «YES», то в следующих n строках выведите по m чисел — высоты оставшихся стогов. Все оставшиеся ненулевые значения должны быть равны, представлять собой связанную область, и хотя бы одно из этих значений не должно быть изменено.

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

Примеры
Входные данные
2 3 35
10 4 9
9 9 7
Выходные данные
YES
7 0 7 
7 7 7
Входные данные
4 4 50
5 9 1 1
5 1 1 5
5 1 5 5
5 5 7 1
Выходные данные
YES
5 5 0 0 
5 0 0 5 
5 0 5 5 
5 5 5 0
Входные данные
2 4 12
1 1 3 1
1 6 2 4
Выходные данные
NO
Примечание

В первом примере ненулевые значения составляют связную область, значения не превосходят начальных высот стогов. Все ненулевые значения равны 7, а их количество равно 5, значит суммарный объём оставшегося сена равен требуемому значению k = 7·5 = 35. При этом стог, находящийся во второй строке и третьем столбце, остался нетронутым.