#include using namespace std; typedef vector vi; typedef vector vvi; const int INF = ~(1<<31); typedef pair ii; void bail() { cout << "Bugged!\n"; exit(0); } #define MAXV 2010 int q[MAXV], d[MAXV]; struct flow_network { struct edge { int v, nxt, cap; edge(int _v, int _cap, int _nxt) : v(_v), nxt(_nxt), cap(_cap) { } }; int n, *head, *curh; vector e, e_store; flow_network(int _n) : n(_n) { curh = new int[n]; memset(head = new int[n], -1, n*sizeof(int)); } void reset() { e = e_store; } void add_edge(int u, int v, int uv, int vu=0) { e.push_back(edge(v,uv,head[u])); head[u]=(int)e.size()-1; e.push_back(edge(u,vu,head[v])); head[v]=(int)e.size()-1;} int augment(int v, int t, int f) { if (v == t) return f; for (int &i = curh[v], ret; i != -1; i = e[i].nxt) if (e[i].cap > 0 && d[e[i].v] + 1 == d[v]) if ((ret = augment(e[i].v, t, min(f, e[i].cap))) > 0) return (e[i].cap -= ret, e[i^1].cap += ret, ret); return 0; } int max_flow(int s, int t, bool res=true) { e_store = e; int l, r, f = 0, x; while (true) { memset(d, -1, n*sizeof(int)); l = r = 0, d[q[r++] = t] = 0; while (l < r) for (int v = q[l++], i = head[v]; i != -1; i=e[i].nxt) if (e[i^1].cap > 0 && d[e[i].v] == -1) d[q[r++] = e[i].v] = d[v]+1; if (d[s] == -1) break; memcpy(curh, head, n * sizeof(int)); while ((x = augment(s, t, INF)) != 0) f += x; } if (res) reset(); return f; } }; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, m; cin >> n >> m; vector inp(n); for(int i = 0; i < n; ++i) cin >> inp[i]; inp.push_back(string(m, 'X')); n++; vi gyrow(n, 0), gycol(m, 0); vector> crossings(n, set()); int xcnt = 0, sigma; cin >> sigma; for(int i = 0; i < n; ++i) { for(int j = 0; j < m; ++j) { if(inp[i][j] == 'G') xcnt++; else { gyrow[i]++; gycol[j]++; crossings[i].insert(j); } } if(i > 0 && gyrow[i] < gyrow[i - 1]) bail(); } if(xcnt + m > sigma) bail(); vector srt; for(int i = 0; i < m; ++i) srt.emplace_back(gycol[i], i); sort(srt.rbegin(), srt.rend()); for(int i = 0; i < m - gyrow[0]; ++i) { int j = srt[i].second; inp.back()[j] = 'G'; gycol[j]--; gyrow.back()--; crossings.back().erase(j); } int cur_char = 1; vvi outp(n, vi(m, -1)); while(gyrow.back() > 0) { int k = gyrow.back(); int maximal = 0, ex_flow = 0; flow_network fw(m + n + 4); for(int i = 0; i < n; ++i) { for(int j : crossings[i]) { fw.add_edge(m + i, j, 1); } if(gyrow[i] == k) fw.add_edge(m + n, m + i, 1), ex_flow++; } for(int i = 0; i < m; ++i) { if(gycol[i] == k) fw.add_edge(i, m + n + 3, 1), maximal++; else fw.add_edge(i, m + n + 2, 1); } if(maximal > ex_flow) bail(); fw.add_edge(m + n + 3, m + n + 1, maximal); fw.add_edge(m + n + 2, m + n + 1, ex_flow - maximal); if(fw.max_flow(m + n, m + n + 1, false) != ex_flow) bail(); for(int i = 0; i < (int) fw.e.size(); ++i) { if(fw.e[i].cap != 0) continue; if(fw.e_store[i].cap == 0) continue; int a = fw.e[i].v, b = fw.e[i ^ 1].v; if(a >= m + n || b >= m + n) continue; if(a > b) swap(a, b); b -= m; outp[b][a] = cur_char; crossings[b].erase(a); gyrow[b]--; gycol[a]--; } cur_char++; } for(int i = 0; i < n; ++i) { for(int j = 0; j < m; ++j) { if(outp[i][j] == -1) outp[i][j] = cur_char++; cout << outp[i][j] << ' '; } cout << '\n'; } }