Даже белым медведям холодно лежать на льду. И вот, белая медведица Алиса собралась сделать ковер. Ковер можно рассматривать как сетку с высотой h и шириной w. Затем сетка делится на h × w квадратов. Алиса собирается покрасить в один из k различных цветов каждый квадрат. Цвета пронумерованы от 1 до k. Она может не использовать все доступные ей цвета.
Однако есть ограничения. Для любых двух соседних ячеек (ячеек, имеющих общую сторону) x и y, есть цветовое ограничение в одной из следующих форм:
- color(x) = color(y), или
- color(x) ≠ color(y).
Пример цветовых ограничений:
В идеале Алиса хочет удовлетворить всем цветовым ограничениям. Но как мы уже говорили, жизнь в Арктике — не сахар. Не всегда можно удовлетворить всех цветовым ограничениям. К счастью, медведица все же будет рада, даже если хотя бы 
цветовых ограничений будут удовлетворены.
Если у Алисы есть 4 цвета, она может раскрасить изображенный на рисунке ковер следующим образом:
И она рада, потому что 
цветовых ограничений удовлетворены и 
. Ваша задача — помочь ей раскрасить ковер.
Выходные данные
Если существует раскраска, удовлетворяющая по крайней мере цветовых ограничений, выведите в первой строке «YES» (без кавычек). В каждой из следующих h строк выведите по w целых чисел, описывающих раскраску.
В противном случае выведите «NO» (без кавычек).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 4 4
ENE
NNEE
NEE
ENEN
ENN
|
YES
1 1 2 2
3 4 1 1
3 3 2 4
|