У фермера Поликарпа есть склад с сеном, который можно представить как прямоугольную таблицу n × m, где n — количество строк, а m — количество столбцов в таблице. В каждой клетке таблицы содержится стог сена. Высота в метрах стога, расположенного в i-й строке и j-м столбце, равна целому числу ai, j и совпадает с количеством кубометров сена в данном стоге, поскольку все клетки имеют размер основания 1 × 1.
Поликарп решил навести на складе порядок, сняв некоторое целое количество кубометров сена с верхушки каждого стога. С разных стогов разрешается снимать различный объем сена. В том числе стог разрешается не трогать совсем или, наоборот, убирать полностью. Если стог убран полностью, то соответствующая клетка становится пустой и стога более не содержит.
Поликарп хочет, чтобы после реорганизации выполнялись следующие требования:
- суммарный объём сена на складе должен быть в точности равен k,
- высоты всех стогов (то есть клеток, содержащих ненулевое количество сена) должны быть одинаковыми,
- высота хотя бы одного стога должна остаться такой же, как была,
- для устойчивости оставшейся конструкции все стога должны представлять собой одну связную область.
Два стога считаются соседними, если они имеют общую сторону в таблице. Область называется связной, если от любого стога этой области можно добраться до любого другого стога этой области, двигаясь только по соседним стогам. При этом два соседних стога обязательно принадлежат одной области.
Помогите Поликарпу выполнить это нелёгкое задание или сообщите, что это невозможно.
Выходные данные
В первой строке выведите «YES», если Поликарп сможет совершить реорганизацию, и «NO» в противном случае. Если ответ «YES», то в следующих n строках выведите по m чисел — высоты оставшихся стогов. Все оставшиеся ненулевые значения должны быть равны, представлять собой связанную область, и хотя бы одно из этих значений не должно быть изменено.
Если существует несколько ответов, разрешается вывести любой из них.
Примечание
В первом примере ненулевые значения составляют связную область, значения не превосходят начальных высот стогов. Все ненулевые значения равны 7, а их количество равно 5, значит суммарный объём оставшегося сена равен требуемому значению k = 7·5 = 35. При этом стог, находящийся во второй строке и третьем столбце, остался нетронутым.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 3 35
10 4 9
9 9 7
|
YES
7 0 7
7 7 7
|
|
2
|
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
|
|
3
|
2 4 12
1 1 3 1
1 6 2 4
|
NO
|