即使是北极熊躺在冰上也会感到寒冷。因此,北极熊爱丽丝要制作地毯。地毯可以看作是高度为 h 、宽度为 w 的网格。然后将网格划分为 h × w 的方格。 Alice 将为每个方块分配 k 种不同颜色中的一种。颜色从 1 到 k 编号。她可能选择不使用所有颜色。
但是,有一些限制。对于每两个相邻的正方形(共享一条边的正方形)x 和 y,存在以下形式之一的颜色约束:
- 颜色(x) = 颜色(y),或
- 颜色(x) ≠ 颜色(y)。
颜色限制示例:
理想情况下,Alice 希望满足所有颜色限制。但同样,北极的生活很艰难。并不总是能够满足所有颜色限制。幸运的是,如果至少满足 $$\frac{3}{4}$$ 的颜色约束,她仍然会很高兴。
如果她有 4 种颜色,她可以按以下方式为地毯着色:
她很高兴,因为满足了 $${ \frac { 1 3 } { 1 7 } }$$ 颜色约束,并且 $$\frac{13}{17} \geq \frac{3}{4}$$。你的任务是帮助她给地毯上色。
输入
第一行包含三个整数 h、w、k (2 ≤ h, w ≤ 1000, 1 ≤ k ≤ w·h)。
接下来的 2h - 1 行从上到下、从左到右描述了颜色约束。它们分别包含 w - 1、w、w - 1、w、...、w - 1 个字符。每个颜色约束由字符“E”或“N”表示,其中“E”表示“=”,“N”表示“≠”。
颜色限制按照它们在图片上描绘的顺序列出。
输出
如果有一种颜色至少满足 $$\frac{3}{4}$$ 的颜色约束,则在第一行打印“YES”(不带引号)。在接下来的 h 行中,打印 w 个描述颜色的整数。
否则,打印“NO”(不带引号)。
示例
输入 #1
3 4 4 ENE NNEE NEE ENEN ENN
输出 #1
YES 1 1 2 2 3 4 1 1 3 3 2 4