#include using namespace std; using ll = long long; using pii = pair; template using V = vector; template using VV = V>; #define pb push_back #define eb emplace_back #define mp make_pair #define fi first #define se second #define rep(i, n) rep2(i, 0, n) #define rep2(i, m, n) for (int i = m; i < (n); i++) #define per(i, b) per2(i, 0, b) #define per2(i, a, b) for (int i = int(b) - 1; i >= int(a); i--) #define ALL(c) (c).begin(), (c).end() constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); } template void chmin(T& t, const U& u) { if (t > u) t = u; } template void chmax(T& t, const U& u) { if (t < u) t = u; } template ostream& operator<<(ostream& os, const pair& p) { os << "(" << p.first << "," << p.second << ")"; return os; } template ostream& operator<<(ostream& os, const vector& v) { os << "{"; rep(i, v.size()) { if (i) os << ","; os << v[i]; } os << "}"; return os; } #ifdef LOCAL void debug_out() { cerr << endl; } template void debug_out(Head H, Tail... T) { cerr << " " << H; debug_out(T...); } #define debug(...) \ cerr << __LINE__ << " [" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #define dump(x) cerr << __LINE__ << " " << #x << " = " << (x) << endl #else #define debug(...) (void(0)) #define dump(x) (void(0)) #endif // O(V^2 E) struct Dinic { using F = ll; static constexpr F INF = numeric_limits::max(); struct Edge { int to, rev; F cap, gen; Edge(int to, F cap, int rev) : to(to), cap(cap), gen(cap), rev(rev){}; }; using E = Edge; VV g; V level, iter; Dinic() {} Dinic(int n) : g(n), level(n), iter(n) {} void add_edge(int from, int to, F cap) { g[from].emplace_back(to, cap, (int)g[to].size()); g[to].emplace_back(from, 0, (int)g[from].size() - 1); } void bfs(int s) { fill(ALL(level), -1); queue que; level[s] = 0; que.push(s); while (!que.empty()) { int v = que.front(); que.pop(); for (auto& e : g[v]) { if (e.cap > 0 && level[e.to] < 0) { level[e.to] = level[v] + 1; que.push(e.to); } } } } F dfs(int v, int t, F f) { if (v == t) return f; for (int& i = iter[v]; i < g[v].size(); i++) { auto& e = g[v][i]; if (e.cap > 0 && level[v] < level[e.to]) { F d = dfs(e.to, t, min(f, e.cap)); if (d > 0) { e.cap -= d; g[e.to][e.rev].cap += d; return d; } } } return 0; } F max_flow(int s, int t) { F flow = 0; while (true) { bfs(s); if (level[t] < 0) return flow; fill(ALL(iter), 0); F f; while ((f = dfs(s, t, INF)) > 0) flow += f; } } }; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int H, W; cin >> H >> W; V A(H), B(W); rep(i, H) cin >> A[i]; rep(i, W) cin >> B[i]; int K; cin >> K; V xs, ys; set ngs; rep(i, K) { int x, y; cin >> x >> y; --x, --y; ngs.insert(mp(x, y)); xs.pb(x), ys.pb(y); } ll s1 = 0, s2 = 0; rep(i, H) s1 += A[i]; rep(i, W) s2 += B[i]; if (s1 != s2) { cout << ":(" << endl; return 0; } sort(ALL(xs)); xs.erase(unique(ALL(xs)), xs.end()); sort(ALL(ys)); ys.erase(unique(ALL(ys)), ys.end()); V hid(H, -1), wid(W, -1); rep(i, xs.size()) hid[xs[i]] = i; rep(i, ys.size()) wid[ys[i]] = i; int node_cnt = xs.size() + ys.size() + 4; int s = node_cnt - 2, t = node_cnt - 1; ll rema = 0, remb = 0; rep(i, H) if (hid[i] == -1) rema += A[i]; rep(i, W) if (wid[i] == -1) remb += B[i]; debug(xs, ys, rema, remb); Dinic flow(node_cnt); flow.add_edge(xs.size(), xs.size() + ys.size() + 1, (H - xs.size()) * (W - ys.size())); flow.add_edge(s, xs.size(), rema); flow.add_edge(xs.size() + ys.size() + 1, t, remb); rep(i, xs.size()) { int x = xs[i]; debug(i, x); flow.add_edge(s, i, A[x]); rep(j, ys.size()) { pii pt(xs[i], ys[j]); if (!ngs.count(pt)) { flow.add_edge(x, xs.size() + 1 + j, 1); } } flow.add_edge(i, xs.size() + ys.size() + 1, W - ys.size()); } rep(j, ys.size()) { int y = ys[j]; debug(j, y); flow.add_edge(xs.size() + 1 + j, t, B[y]); flow.add_edge(xs.size(), xs.size() + 1 + j, H - xs.size()); } auto fl = flow.max_flow(s, t); VV cands(node_cnt); rep(i, H) { if (hid[i] == -1) cands[xs.size()].pb(i); else cands[hid[i]].pb(i); } rep(j, W) { if (wid[j] == -1) cands[xs.size() + ys.size() + 1].pb(j); else cands[xs.size() + 1 + wid[j]].pb(j); } debug(fl, s1); if (fl != s1) { cout << ":(" << endl; return 0; } V ans(H, string(W, '.')); for (auto p : ngs) { ans[p.fi][p.se] = 'x'; } rep(i, xs.size() + 1) { V es; for (auto e : flow.g[i]) { if (e.to >= xs.size() + 1 && e.to <= xs.size() + ys.size() + 1) { int cnt = e.gen - e.cap; es.eb(e.to, cnt); } } sort(ALL(es)); for (auto e : es) { int to = e.fi, cnt = e.se; debug(cnt); if (i != xs.size()) { priority_queue yque; for (int y : cands[to]) { if (B[y] > 0) yque.push(mp(B[y], y)); } debug(cands[i], cands[to]); for (int x : cands[i]) { V nx; while (A[x] > 0 && cnt > 0) { if (yque.size() == 0) { cout << ":(" << endl; return 0; } cnt--; A[x]--; pii py = yque.top(); yque.pop(); py.fi--; B[py.se]--; nx.eb(py); ans[x][py.se] = 'o'; } for (auto p : nx) yque.push(p); } if (cnt > 0) { cout << ":(" << endl; return 0; } } else { priority_queue xque; for (int x : cands[i]) { if (A[x] > 0) xque.push(mp(A[x], x)); } debug(cands[i], cands[to]); for (int y : cands[to]) { V nx; while (B[y] > 0 && cnt > 0) { if (xque.size() == 0) { cout << ":(" << endl; return 0; } cnt--; B[y]--; pii px = xque.top(); xque.pop(); px.fi--; A[px.se]--; nx.eb(px); ans[px.se][y] = 'o'; } for (auto p : nx) xque.push(p); } if (cnt > 0) { cout << ":(" << endl; return 0; } } } } cout << "Yay!" << endl; rep(i, H) cout << ans[i] << '\n'; return 0; }