#include using namespace std; using lint = long long; using pint = pair; using plint = pair; struct fast_ios { fast_ios(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_; #define ALL(x) (x).begin(), (x).end() #define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i=i##_begin_;i--) #define REP(i, n) FOR(i,0,n) #define IREP(i, n) IFOR(i,0,n) template void ndarray(vector &vec, int len) { vec.resize(len); } template void ndarray(vector &vec, int len, Args... args) { vec.resize(len); for (auto &v : vec) ndarray(v, args...); } template void ndfill(V &x, const T &val) { x = val; } template void ndfill(vector &vec, const T &val) { for (auto &v : vec) ndfill(v, val); } template bool chmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; } template bool chmin(T &m, const T q) { if (m > q) {m = q; return true;} else return false; } template pair operator+(const pair &l, const pair &r) { return make_pair(l.first + r.first, l.second + r.second); } template pair operator-(const pair &l, const pair &r) { return make_pair(l.first - r.first, l.second - r.second); } template vector srtunq(vector vec) { sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end()); return vec; } template istream &operator>>(istream &is, vector &vec) { for (auto &v : vec) is >> v; return is; } template istream &operator>>(istream &is, tuple &tpl) { std::apply([&is](auto &&... args) { ((is >> args), ...);}, tpl); return is; } template ostream &operator<<(ostream &os, const vector &vec) { os << '['; for (auto v : vec) os << v << ','; os << ']'; return os; } template ostream &operator<<(ostream &os, const tuple &tpl) { std::apply([&os](auto &&... args) { ((os << args << ','), ...);}, tpl); return os; } template ostream &operator<<(ostream &os, const deque &vec) { os << "deq["; for (auto v : vec) os << v << ','; os << ']'; return os; } template ostream &operator<<(ostream &os, const set &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; } template ostream &operator<<(ostream &os, const unordered_set &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; } template ostream &operator<<(ostream &os, const multiset &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; } template ostream &operator<<(ostream &os, const unordered_multiset &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; } template ostream &operator<<(ostream &os, const pair &pa) { os << '(' << pa.first << ',' << pa.second << ')'; return os; } template ostream &operator<<(ostream &os, const map &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; } template ostream &operator<<(ostream &os, const unordered_map &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; } #define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl; bool muri() { puts(":("); exit(0); } // MaxFlow (Dinic algorithm) template struct MaxFlow { struct edge { int to; T cap; int rev; }; std::vector> edges; std::vector level; // level[i] = distance between vertex S and i (Default: -1) std::vector iter; // iteration counter, used for Dinic's DFS std::vector used; // Used for Ford-Fulkerson's Algorithm void bfs(int s) { level.assign(edges.size(), -1); std::queue q; level[s] = 0; q.push(s); while (!q.empty()) { int v = q.front(); q.pop(); for (edge &e : edges[v]) { if (e.cap > 0 and level[e.to] < 0) { level[e.to] = level[v] + 1; q.push(e.to); } } } } T dfs_dinic(int v, int goal, T f) { if (v == goal) return f; for (int &i = iter[v]; i < (int)edges[v].size(); i++) { edge &e = edges[v][i]; if (e.cap > 0 and level[v] < level[e.to]) { T d = dfs_dinic(e.to, goal, std::min(f, e.cap)); if (d > 0) { e.cap -= d; edges[e.to][e.rev].cap += d; return d; } } } return 0; } T dfs_ff(int v, int goal, T f) { if (v == goal) return f; used[v] = true; for (edge &e : edges[v]) { if (e.cap > 0 && !used[e.to]) { T d = dfs_ff(e.to, goal, std::min(f, e.cap)); if (d > 0) { e.cap -= d; edges[e.to][e.rev].cap += d; return d; } } } return 0; } public: MaxFlow(int N) { edges.resize(N); } void add_edge(int from, int to, T capacity) { edges[from].push_back(edge{to, capacity, (int)edges[to].size()}); edges[to].push_back(edge{from, (T)0, (int)edges[from].size() - 1}); } // Dinic algorithm // Complexity: O(VE) T Dinic(int s, int t) { constexpr T INF = std::numeric_limits::max(); T flow = 0; while (true) { bfs(s); if (level[t] < 0) return flow; iter.assign(edges.size(), 0); T f; while ((f = dfs_dinic(s, t, INF)) > 0) flow += f; } } // Ford-Fulkerson algorithm // Complexity: O(EF) T FF(int s, int t) { constexpr T INF = std::numeric_limits::max(); T flow = 0; while (true) { used.assign(edges.size(), 0); T f = dfs_ff(s, t, INF); if (f == 0) return flow; flow += f; } } void back_flow(int s, int t, int s_e, int t_e, T capacity_reduce) { int i; for (i=0; edges[s_e][i].to != t_e; ) i++; edge &e = edges[s_e][i]; if (capacity_reduce <= e.cap) { e.cap -= capacity_reduce; } else { T flow = capacity_reduce - e.cap; e.cap = 0; edges[e.to][e.rev].cap -= flow; T f_sum = 0; while (f_sum != flow) { used.assign(edges.size(), 0); f_sum += dfs_ff(t, t_e, flow - f_sum); } f_sum = 0; while (f_sum != flow) { used.assign(edges.size(), 0); f_sum += dfs_ff(s_e, s, flow - f_sum); } } } }; int main() { int H, W; cin >> H >> W; vector A(H), B(W); cin >> A >> B; int K; cin >> K; vector X(K), Y(K); vector> bad(H, vector(W)); REP(i, K) { cin >> X[i] >> Y[i]; X[i]--, Y[i]--; bad[X[i]][Y[i]] = 1; } const vector xu = srtunq(X), yu = srtunq(Y); vector xsp(H), ysp(W); for (auto x : xu) xsp[x] = 1; for (auto y : yu) ysp[y] = 1; int P = xu.size(), Q = yu.size(); int atot = accumulate(ALL(A), 0), btot = accumulate(ALL(B), 0); if (atot != btot) muri(); int allflow = atot; vector ret(H, string(W, '.')); REP(i, H) REP(j, W) if (bad[i][j]) ret[i][j] = 'x'; { int T = 1 + P + 1 + Q + 1; MaxFlow flow(T + 1); REP(i, P) flow.add_edge(0, i + 1, A[xu[i]]), atot -= A[xu[i]], flow.add_edge(i + 1, P + Q + 2, W - yu.size()); flow.add_edge(0, P + 1, atot); REP(i, Q) flow.add_edge(P + 2 + i, T, B[yu[i]]), btot -= B[yu[i]], flow.add_edge(P + 1, P + 2 + i, H - xu.size()); flow.add_edge(P + Q + 2, T, btot); flow.add_edge(P + 1, P + Q + 2, (H - xu.size()) * (W - yu.size())); REP(i, P) REP(j, Q) if (!bad[xu[i]][yu[j]]) flow.add_edge(i + 1, P + 2 + j, 1); if (allflow != flow.Dinic(0, T)) muri(); REP(i, P) for (auto e : flow.edges[1 + i]) { if (e.to >= P + 2 and e.to < P + Q + 2 and e.cap == 0) { int x = xu.at(i); int y = yu.at(e.to - P - 2); A[x]--, B[y]--, ret[x][y] = 'o'; } } } { int T = 1 + P + W; MaxFlow fx(T + 1); int allflow = 0; REP(i, P) fx.add_edge(0, 1 + i, A[xu[i]]), allflow += A[xu[i]]; REP(i, P) REP(y, W) if (!ysp[y] and ret[xu[i]][y] == '.') fx.add_edge(1 + i, 1 + P + y, 1); REP(y, W) if (!ysp[y] and B[y]) fx.add_edge(1 + P + y, T, B[y]); if (allflow != fx.Dinic(0, T)) muri(); REP(i, P) for (auto e : fx.edges[1 + i]) { if (e.to >= P + 1 and e.to <= P + W and e.cap == 0) { int x = xu.at(i); int y = e.to - P - 1; A[x]--, B[y]--, ret[x][y] = 'o'; } } } { int T = 1 + Q + H; MaxFlow fy(T + 1); int allflow = 0; REP(i, Q) fy.add_edge(0, 1 + i, B[yu[i]]), allflow += B[yu[i]]; REP(j, Q) REP(x, H) if (ret[x][yu[j]] == '.') fy.add_edge(1 + j, 1 + Q + x, 1); REP(x, H) if (!xsp[x] and A[x]) fy.add_edge(1 + Q + x, T, A[x]); if (allflow != fy.Dinic(0, T)) muri(); REP(i, Q) for (auto e : fy.edges[1 + i]) { if (e.to >= Q + 1 and e.to <= Q + H and e.cap == 0) { int y = yu.at(i); int x = e.to - Q - 1; A[x]--, B[y]--, ret[x][y] = 'o'; } } } priority_queue pqx, pqy; REP(i, A.size()) if (A[i]) pqx.push(pint(A[i], i)); REP(i, B.size()) if (B[i]) pqy.push(pint(B[i], i)); REP(i, A.size()) if (A[i]) assert(!xsp[i]); REP(i, B.size()) if (B[i]) assert(!ysp[i]); while (pqx.size()) { auto [sz, x] = pqx.top(); pqx.pop(); vector q; while (sz) { sz--; if (pqy.empty()) muri(); auto [s_, y] = pqy.top(); pqy.pop(); ret[x][y] = 'o'; s_--; if (s_) q.emplace_back(s_, y); } for (auto p : q) pqy.push(p); } if (pqx.size()) muri(); cout << "Yay!\n"; for (auto str : ret) cout << str << '\n'; }