#include /** * @title Graph template * @docs graph_template.md */ template class Edge{ public: int from,to; Cost cost; Edge() {} Edge(int to, Cost cost): to(to), cost(cost){} Edge(int from, int to, Cost cost): from(from), to(to), cost(cost){} }; template using Graph = std::vector>>; template using Tree = std::vector>>; template void add_edge(C &g, int from, int to, T w = 1){ g[from].emplace_back(from, to, w); } template void add_undirected(C &g, int a, int b, T w = 1){ add_edge(g, a, b, w); add_edge(g, b, a, w); } /** * @title Topological sort * @docs topological_sort.md */ template std::optional> topological_sort(const Graph &g){ const int n = g.size(); std::vector indeg(n); for(int i = 0; i < n; ++i){ for(auto &e : g[i]){ ++indeg[e.to]; } } std::queue q; for(int i = n-1; i >= 0; --i){ if(indeg[i] == 0) q.push(i); } std::vector ret; while(!q.empty()){ int cur = q.front(); q.pop(); ret.push_back(cur); for(auto &e : g[cur]){ --indeg[e.to]; if(indeg[e.to] == 0){ q.push(e.to); } } } if((int)ret.size() == n){ return {ret}; }else{ return std::nullopt; } } /** * @title Strongly connected components * @docs strongly_connected_components.md */ template auto strongly_connected_components(const Graph &g){ const int n = g.size(); std::vector visit(n); std::vector check(n); std::vector result(n, -1); auto dfs = [&](auto &f, int cur) -> void { visit[cur] = true; for(const auto &e : g[cur]){ if(not visit[e.to]) f(f, e.to); } check.push_back(cur); }; for(int i = 0; i < n; ++i) if(not visit[i]) dfs(dfs, i); std::reverse(check.begin(), check.end()); Graph rg(n); auto rdfs = [&](auto &f, int cur, int i) -> void { result[cur] = i; for(const auto &e : rg[cur]){ if(result[e.to] == -1) f(f, e.to, i); } }; for(int i = 0; i < n; ++i) for(const auto &e : g[i]) rg[e.to].emplace_back(e.to, e.from, e.cost); int i = 0; for(auto c : check) if(result[c] == -1) rdfs(rdfs, c, i), ++i; return std::make_pair(result, i); } /** * @title 2-SAT * @docs two_sat.md */ class TwoSat{ const int n; Graph g; int f(int i){ assert(i != 0); assert(abs(i) <= n); if(i > 0) return i-1; else return abs(i)-1 + n; } public: TwoSat(int n): n(n), g(2*n){} /** * @note a→bを導入する */ void add_if(int a, int b){ add_edge(g, f(a), f(b), 1); } /** * @note a∨bを導入する * @note a ∨ b <=> (!a => b) ∧ (!b => a) */ void add_or(int a, int b){ add_if(-a, b); add_if(-b, a); } /** * @note ¬(a∧b)を導入する * @note !(A ∧ B) <=> (!A ∨ !B) */ void not_coexist(int a, int b){ add_or(-a, -b); } public: std::optional> solve() const { auto [scc, m] = strongly_connected_components(g); for(int i = 0; i < n; ++i){ if(scc[i] == scc[i+n]) return {}; } Graph g2(m); for(int i = 0; i < 2*n; ++i){ for(auto &e : g[i]){ if(scc[e.from] != scc[e.to]){ add_edge(g2, scc[e.from], scc[e.to], 1); } } } auto ts = *topological_sort(g2); std::vector r(m); for(int i = 0; i < m; ++i) r[ts[i]] = i; std::vector ret(n); for(int i = 0; i < n; ++i) ret[i] = r[scc[i]] > r[scc[i+n]]; return {ret}; } }; int main(){ int N; std::cin >> N; std::vector S(N), T(N), U(N); for(int i = 0; i < N; ++i) std::cin >> S[i], --S[i]; for(int i = 0; i < N; ++i) std::cin >> T[i], --T[i]; for(int i = 0; i < N; ++i) std::cin >> U[i]; TwoSat sat(N*N); auto index = std::vector(N, std::vector(N)); { int k = 1; for(int i = 0; i < N; ++i){ for(int j = 0; j < N; ++j){ index[i][j] = k; ++k; } } } for(int i = 0; i < N; ++i){ for(int j = 0; j < N; ++j){ switch(U[i]){ case 0: sat.not_coexist(-index[S[i]][j], -index[j][T[i]]); break; case 1: sat.not_coexist(index[S[i]][j], -index[j][T[i]]); break; case 2: sat.not_coexist(-index[S[i]][j], -index[j][T[i]]); break; case 3: sat.not_coexist(index[S[i]][j], index[j][T[i]]); break; } } } auto res = sat.solve(); if(res){ for(int i = 0; i < N; ++i){ for(int j = 0; j < N; ++j){ std::cout << (*res)[index[i][j]-1] << " "; } std::cout << "\n"; } }else{ std::cout << -1 << "\n"; } return 0; }