// ---------- begin Strongly Connected Components ---------- struct SCC { size: usize, edge: Vec<(usize, usize)>, id: Vec, } impl SCC { pub fn new(size: usize) -> Self { SCC { size: size, edge: vec![], id: Vec::with_capacity(size), } } pub fn add_edge(&mut self, from: usize, to: usize) { assert!(from < self.size && to < self.size); self.edge.push((from, to)); } fn build_graph<'a>(&self, buf: &'a mut [usize], cnt: &[usize], inv: bool) -> Vec<&'a mut [usize]> { let size = self.size; let mut index = vec![0; self.size]; for e in self.edge.iter() { let (f, t) = if inv { (e.1, e.0) } else { *e }; buf[self.edge.len() - cnt[f] + index[f]] = t; index[f] += 1; } let mut ans = Vec::with_capacity(size); let mut buf = Some(buf); for i in 0..size { let len = cnt[i] - cnt[i + 1]; let x = buf.take().unwrap(); let (x, y) = x.split_at_mut(len); ans.push(x); buf = Some(y); } ans } fn dfs1(&self, buf: &mut [usize], cnt: &[usize], q: &mut Vec) { let size = self.size; let graph = self.build_graph(buf, cnt, false); let mut visited = vec![false; size]; let mut stack = vec![]; for v in 0..size { if visited[v] { continue; } stack.clear(); visited[v] = true; stack.push((v, graph[v].iter())); while let Some((v, mut it)) = stack.pop() { let mut finish = true; while let Some(&u) = it.next() { if !visited[u] { visited[u] = true; finish = false; stack.push((v, it)); stack.push((u, graph[u].iter())); break; } } if finish { q.push(v); } } } } fn dfs2(&mut self, buf: &mut [usize], cnt: &[usize], q: &[usize]) { let size = self.size; let inv_graph = self.build_graph(buf, cnt, true); self.id.clear(); self.id.resize(size, size); let mut counter = 0; let mut stack = vec![]; for &v in q.iter().rev() { if self.id[v] < size { continue; } self.id[v] = counter; stack.clear(); stack.push(v); while let Some(v) = stack.pop() { self.id[v] = counter; for &u in inv_graph[v].iter() { if self.id[u] == size { self.id[u] = counter; stack.push(u); } } } counter += 1; } } pub fn build(&mut self) { let size = self.size; let mut cnt = vec![0; size + 1]; let mut inv_cnt = vec![0; size + 1]; for e in self.edge.iter() { cnt[e.0] += 1; inv_cnt[e.1] += 1; } for i in (0..size).rev() { cnt[i] += cnt[i + 1]; inv_cnt[i] += inv_cnt[i + 1]; } let mut buf = vec![0; self.edge.len()]; let mut q = Vec::with_capacity(size); self.dfs1(&mut buf, &cnt, &mut q); self.dfs2(&mut buf, &inv_cnt, &q); } pub fn get_array(&self) -> Vec { self.id.clone() } } // ---------- end Strongly Connected Components ---------- // ---------- begin 2-SAT ---------- struct SAT2 { size: usize, scc: SCC, } impl SAT2 { fn new(size: usize) -> Self { SAT2 { size: size, scc: SCC::new(2 * size), } } fn add(&mut self, a: usize, b: usize) { let size = self.size; let (x, ix) = if a >= size { (!a + size, !a) } else { (a, a + size) }; let (y, iy) = if b >= size { (!b + size, !b) } else { (b, b + size) }; self.scc.add_edge(ix, y); self.scc.add_edge(iy, x); } fn solve(&mut self) -> Option> { self.scc.build(); let id = self.scc.get_array(); let mut ans = vec![]; for i in 0..self.size { if id[i] == id[i + self.size] { return None; } else if id[i] < id[i + self.size] { ans.push(false); } else { ans.push(true); } } Some(ans) } } // ---------- end 2-SAT ---------- use std::io::Read; fn run() { let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); let mut it = s.trim().split_whitespace(); let n: usize = it.next().unwrap().parse().unwrap(); let s: Vec = (0..n).map(|_| { it.next().unwrap().parse::().unwrap() - 1 }).collect(); let t: Vec = (0..n).map(|_| { it.next().unwrap().parse::().unwrap() - 1 }).collect(); let u: Vec = it.map(|s| s.parse().unwrap()).collect(); let mut sat = SAT2::new(n * n); for i in 0..n { for j in 0..n { let x = s[i] * n + j; let y = j * n + t[i]; match u[i] { 0 => { sat.add(x, y); }, 1 => { sat.add(!x, y); }, 2 => { sat.add(x, !y) }, 3 => { sat.add(!x, !y); }, _ => unreachable!(), } } } if let Some(a) = sat.solve() { let mut out = String::new(); for i in 0..n { for j in 0..n { let a = a[i * n + j]; out.push_str(&format!("{} ", a as usize)); } out.pop(); out.push('\n'); } print!("{}", out); } else { println!("-1"); } } fn main() { run(); }