CF297D.Color the Carpet

Even polar bears feel cold when lying on the ice. Therefore, a polar bear Alice is going to make a carpet. The carpet can be viewed as a grid with height h and width w. Then the grid is divided into h × w squares. Alice is going to assign one of k different colors to each square. The colors are numbered from 1 to k. She may choose not to use all of the colors.

However, there are some restrictions. For every two adjacent squares (squares that shares an edge) x and y, there is a color constraint in one of the forms:

• color(x) = color(y), or
• color(x) ≠ color(y).

Example of the color constraints:

Ideally, Alice wants to satisfy all color constraints. But again, life in the Arctic is hard. It is not always possible to satisfy all color constraints. Fortunately, she will still be happy if at least of the color constraints are satisfied.

If she has 4 colors she can color the carpet in the following way:

And she is happy because of the color constraints are satisfied, and . Your task is to help her color the carpet.

即使是北极熊在冰面上躺着时也会感到寒冷。因此，一只名叫爱丽丝的北极熊打算制作一张地毯。这张地毯可以看作是一个高度为 $h$、宽度为 $w$ 的网格，被划分为 $h \times w$ 个方格。爱丽丝将为每个方格分配 $k$ 种不同颜色中的一种，这些颜色编号为 $1$ 到 $k$。她可以选择不使用全部 $k$ 种颜色。

然而，存在一些限制条件：对于任意两个相邻的方格（即共享一条边的方格）$x$ 和 $y$，均存在如下形式之一的颜色约束：

• $\text{color}(x) = \text{color}(y)$，或
• $\text{color}(x) \ne \text{color}(y)$。

颜色约束示例：

理想情况下，爱丽丝希望满足所有颜色约束。但再次说明，北极的生活十分艰难——并不总能同时满足全部约束。幸运的是，只要至少满足 的颜色约束，她就会感到满意。

例如，若她有 4 种颜色，可将地毯按如下方式着色：

此时她感到满意，因为满足了 的颜色约束，且 。你的任务是帮助她为地毯着色。

The first line contains three integers h, w, k (2 ≤ h, w ≤ 1000, 1 ≤ k ≤ w·h).

The next 2_h_ - 1 lines describe the color constraints from top to bottom, left to right. They contain w - 1, w, w - 1, w, ..., w - 1 characters respectively. Each color constraint is represented by a character "E" or "N", where "E" means " = " and "N" means " ≠ ".

The color constraints listed in the order they are depicted on the picture.

第一行包含三个整数 $h$、$w$、$k$（满足 $2 \leq h, w \leq 1000$，$1 \leq k \leq w \cdot h$）。

接下来的 $2h - 1$ 行按从上到下、从左到右的顺序描述颜色约束。这些行分别包含 $w-1$、$w$、$w-1$、$w$、$\dots$、$w-1$ 个字符。每个颜色约束用一个字符 "E" 或 "N" 表示，其中 "E" 表示 “$=$”，"N" 表示 “$\neq$”。

颜色约束的列出顺序与图中所示顺序一致。

If there is a coloring that satisfies at least of the color constraints, print "YES" (without quotes) in the first line. In each of the next h lines, print w integers describing the coloring.

Otherwise, print "NO" (without quotes).

如果存在一种染色方案，满足至少 的颜色约束，则在第一行输出 "YES"（不带引号）。接下来的 h 行中，每行输出 w 个整数，描述该染色方案。

否则，输出 "NO"（不带引号）。