#include // #include using namespace std; // using namespace atcoder; template ostream &operator<<(ostream &os, const pair &p) { os << "(" << p.first << "," << p.second << ")"; return os; } #ifdef __LOCAL #define debug(x) cerr << __LINE__ << ": " << #x << " = " << (x) << '\n' #define debugArray(x, n) \ cerr << __LINE__ << ": " << #x << " = {"; \ for (long long hoge = 0; (hoge) < (long long)(n); ++(hoge)) \ cerr << ((hoge) ? "," : "") << x[hoge]; \ cerr << "}" << '\n' #define debugMatrix(x, h, w) \ cerr << __LINE__ << ": " << #x << " =\n"; \ for (long long hoge = 0; (hoge) < (long long)(h); ++(hoge)) { \ cerr << ((hoge ? " {" : "{{")); \ for (long long fuga = 0; (fuga) < (long long)(w); ++(fuga)) \ cerr << ((fuga ? ", " : "")) << x[hoge][fuga]; \ cerr << "}" << (hoge + 1 == (long long)(h) ? "}" : ",") << '\n'; \ } #else #define debug(x) (void(0)) #define debugArray(x, n) (void(0)) #define debugMatrix(x, h, w) (void(0)) #endif template class MaxFlowLowerBound : public FlowAlgo { using Edge = typename FlowAlgo::Edge; using flow_t = decltype(Edge::cap); std::vector in; int add_edge(int src, int dst, flow_t cap) { int e = this->adj[src].size(); int re = src == dst ? e + 1 : this->adj[dst].size(); this->adj[src].push_back(Edge{dst, re, cap}); this->adj[dst].push_back(Edge{src, e, 0}); return this->m++, re; } public: MaxFlowLowerBound(std::size_t n = 0) : FlowAlgo(n + 2), in(n) {} int add_vertex() { return this->adj.resize(++this->n), in.resize(this->n - 2, 0), this->n - 3; } std::vector add_vertices(const std::size_t size) { std::vector ret(size); std::iota(ret.begin(), ret.end(), this->n - 2); return this->adj.resize(this->n += size), in.resize(this->n - 2, 0), ret; } struct EdgePtr { friend class MaxFlowLowerBound; MaxFlowLowerBound *instance; int v, e; flow_t u; Edge &edge() { return instance->adj[v][e]; } Edge &rev() { Edge &e = edge(); return instance->adj[e.dst][e.rev]; } EdgePtr(MaxFlowLowerBound *instance, int v, int e, flow_t u) : instance(instance), v(v), e(e), u(u) {} public: EdgePtr() = default; int src() { return v; } int dst() { return edge().dst; } flow_t flow() { return u - edge().cap; } flow_t lower() { return flow() - rev().cap; } flow_t upper() { return u; } }; EdgePtr add_edge(int src, int dst, flow_t lower, flow_t upper) { assert(lower <= upper); src += 2, dst += 2; assert(0 <= src && src < this->n); assert(0 <= dst && dst < this->n); this->m++; int e = this->adj[src].size(); int re = src == dst ? e + 1 : this->adj[dst].size(); if (lower * upper <= 0) { this->adj[src].push_back(Edge{dst, re, upper}); this->adj[dst].push_back(Edge{src, e, -lower}); } else if (lower > 0) { in[src - 2] -= lower, in[dst - 2] += lower; this->adj[src].push_back(Edge{dst, re, upper - lower}); this->adj[dst].push_back(Edge{src, e, 0}); } else { in[src - 2] -= upper, in[dst - 2] += upper; this->adj[src].push_back(Edge{dst, re, 0}); this->adj[dst].push_back(Edge{src, e, upper - lower}); } return EdgePtr(this, src, e, upper); } flow_t maxflow(int s, int t) { static constexpr flow_t INF = std::numeric_limits::max(); flow_t sum = 0; for (int i = this->n - 2; i--;) { if (in[i] > 0) add_edge(0, i + 2, in[i]), sum += in[i]; if (in[i] < 0) add_edge(i + 2, 1, -in[i]); } int re = add_edge(t += 2, s += 2, INF); if (this->flow(0, 1, INF) < sum) return -1; // no solution return this->flow(s, t, INF) + this->adj[s][re].cap; } }; template struct Dinic { Dinic(std::size_t _n = 0) : n(_n), m(0), adj(n) {} protected: struct Edge { int dst, rev; flow_t cap; }; int n, m; std::vector> adj; std::vector level, iter; inline void levelize(const int &s, const int &t) { level.assign(n, -1), level[s] = 0; std::queue que; for (que.push(s); !que.empty();) { int u = que.front(); que.pop(); for (auto &e : adj[u]) if (e.cap > 0 && level[e.dst] < 0) { level[e.dst] = level[u] + 1; if (e.dst == t) return; que.push(e.dst); } } } inline flow_t dfs(int u, const int &s, flow_t cur) { if (u == s) return cur; flow_t ret = 0; for (int &i = iter[u]; i < adj[u].size(); i++) { Edge &e = adj[u][i], &re = adj[e.dst][e.rev]; if (level[u] <= level[e.dst] || re.cap == 0) continue; flow_t f = dfs(e.dst, s, std::min(cur - ret, re.cap)); if (f <= 0) continue; e.cap += f, re.cap -= f, ret += f; if (ret == cur) return ret; } return level[u] = n, ret; } flow_t flow(int s, int t, flow_t flow_lim) { assert(0 <= s && s < n); assert(0 <= t && t < n); assert(s != t); flow_t ret = 0; for (flow_t f; ret < flow_lim; ret += f) { if (levelize(s, t), level[t] == -1) break; iter.assign(n, 0); if (!(f = dfs(t, s, flow_lim - ret))) break; } return ret; } }; signed main() { cin.tie(0); ios::sync_with_stdio(false); cin.tie(0); ios::sync_with_stdio(false); int H, W, N; cin >> H >> W >> N; int height[W] = {0}; for (int i = 0; i < H; i++) { string S; cin >> S; for (int j = 0; j < W; j++) height[j] += S[j] == '#'; } using MF = MaxFlowLowerBound>; MF graph; MF::EdgePtr e[N][3]; int s = graph.add_vertex(), t = graph.add_vertex(); auto p = graph.add_vertices(N), q = graph.add_vertices(W); for (int i = 0; i < N; i++) { int C; cin >> C; graph.add_edge(s, p[i], 1, 9); for (int j = 0; j < 3; j++) e[i][j] = graph.add_edge(p[i], q[C + j], 0, 3); } for (int i = 0; i < W; i++) graph.add_edge(q[i], t, height[i], height[i]); graph.maxflow(s, t); for (int i = 0; i < N; i++) { string ans[3] = {"...", "...", "..."}; for (int j = 0; j < 3; j++) { auto f = e[i][j].flow(); for (int k = 0; k < f; k++) ans[k][j] = '#'; } for (int j = 0; j < 3; j++) cout << ans[j] << '\n'; } return 0; return 0; }