Cho một bảng hình chữ nhật gồm $N$ dòng và $M$ cột. Các dòng được đánh số từ 1 đến N, các cột được đánh số từ $1$ đến $M$, giao của dòng $i$ và cột $j$ là ô $(i,j)$. Có $K$ màu được đánh số từ $1$ đến $K$. Cần tô mỗi ô trong bảng bằng một trong $K$ màu trên (không nhất thiết phải sử dụng toàn bộ $K$ màu).

Tuy nhiên, sẽ có các ràng buộc về tương quang màu sắc giữa các ô kề nhau. Các ràng buộc này được mô tả bằng hai bảng kí tự $H$ (gồm $N$ dòng, $M-1$ cột) và $V$ (gồm $N-1$ dòng, $M$ cột). Cụ thể:

• Nếu $H_{i,j}$ = ${}^{\prime }{E}^{\prime }$ thì hai ô $(i,j)$ và $(i,j+1)$ phải cùng màu với nhau, nếu $H_{i,j}$ = ${}^{\prime }{N}^{\prime }$ thì hai ô $(i,j)$ và $(i,j+1)$ phải khác màu với nhau.
• Nếu $V_{i,j}$ = ${}^{\prime }{E}^{\prime }$ thì hai ô $(i,j)$ và $(i+1,j)$ phải cùng màu với nhau, nếu $V_{i,j}$ = ${}^{\prime }{N}^{\prime }$ thì hai ô $(i,j)$ và $(i+1,j)$ phải khác màu với nhau.

Hãy tìm một cách tô màu bất kì sao cho ít nhất $75$% số lượng các ràng buộc trên được thỏa mãn, hoặc in ra $-1$ nếu không có cách tô.

Input

• Dòng đầu tiên gồm số nguyên $N,M,K$ $(2\le N,M\le 1000,1\le K\le N\ast M)$ - số dòng và số cột của bảng chữ nhật
• $N$ dòng tiếp theo, mỗi dòng gồm một xâu độ dài $M-1$, chỉ gồm kí tự ${}^{\prime }{E}^{\prime }$ hoặc ${}^{\prime }{N}^{\prime }$ - bảng kí tự $H$.
• $N-1$ dòng tiếp theo, mỗi dòng gồm một xâu độ dài $M$, chỉ gồm kí tự ${}^{\prime }{E}^{\prime }$ hoặc ${}^{\prime }{N}^{\prime }$ - bảng kí tự $V$.

Output

• Nếu có một cách tô màu thỏa mãn ít nhất $75$% số lượng ràng buộc, in ra $N$ dòng, mỗi dòng gồm $M$ số nguyên có giá trị từ $1$ đến $K$ mô tả cách tô màu cho các ô trong bảng.
• Ngược lại, in ra $-1$

Scoring

• Subtask 1 (10% số điểm): $K$ = 1
• Subtask 2 (20% số điểm): $N\ast M\le 15$
• Subtask 3 (70% số điểm): Không có ràng buộc gì thêm

• Ví dụ

Input

3 4 3
EEN
ENN
NNE
ENEN
NENN

Output

1 2 2 3
1 1 2 3
3 3 1 1

Giải thích ví dụ

Hình vẽ minh họa cho ví dụ. Màu cam tương ứng với màu 1, màu xanh lá cây tương ứng với màu 2, màu xanh biển tương ứng với màu 3. Các kí hiệu màu đen là ràng buộc được thỏa mãn, màu đỏ là ràng buộc không được thỏa mãn.

Có 13 trên 17 ràng buộc được thỏa mãn, tỉ lệ dưới $75$%. Do đó, cách tô màu này thỏa mãn điều kiện đề bài.