#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; } 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; 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(); vector ret(H, string(W, '.')); REP(i, H) REP(j, W) if (bad[i][j]) ret[i][j] = 'x'; 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[i]; int y = yu[e.to - P - 2]; A[x]--, B[y]--, ret[x][y] = 'o'; } } for (auto x : xu) { REP(y, W) if (!ysp[y] and A[x] and B[y] and ret[x][y] == '.') { ret[x][y] = 'o', A[x]--, B[y]--; } } for (auto y : yu) { REP(x, H) if (!xsp[x] and A[x] and B[y] and ret[x][y] == '.') { ret[x][y] = 'o', A[x]--, B[y]--; } } REP(i, H) REP(j, W) if (A[i] and B[j] and ret[i][j] == '.') { A[i]--, B[j]--, ret[i][j] = 'o'; } cout << "Yay!\n"; for (auto str : ret) cout << str << '\n'; }