#![allow(non_snake_case,dead_code,unused_imports)] use proconio::{*,marker::*}; fn main(){ input!{ t:usize, } 'a: for _ in 0..t{ input!{ n:usize, x:[usize;n], y:[usize;n], z:[usize;2*n-1], } let mut tx=vec![0;n]; let mut ty=vec![0;n]; let mut tz=vec![0;2*n-1]; let mut ans=vec![vec![0;n];n]; for i in 0..30{ for (a,ta) in [(&x,&mut tx),(&y,&mut ty),(&z,&mut tz)]{ for j in 0..a.len(){ ta[j]=a[j]>>i&1; } } if let Some(res)=solve(n,&tx,&ty,&tz){ for p in iterp(n,n){ ans[p]|=res[p]<Option>>{ let all1_i=(0..n).filter(|&i|x[i]==1).collect_vec(); let all0_j=(0..n).filter(|&j|y[j]==0).collect_vec(); if all1_i.len()>0 && all0_j.len()>0{ return None; } let check=|ans:&Vec>|->bool{ for i in 0..n{ let mut and=1; for j in 0..n{ and&=ans[i][j]; } if and!=x[i]{ return false; } } for j in 0..n{ let mut or=0; for i in 0..n{ or|=ans[i][j]; } if or!=y[j]{ return false; } } for sum in 0..z.len(){ let mut xor=0; for i in 0..=sum{ let j=sum-i; if i>(i*n+j)&1; } } if check(&ans){ return Some(ans); } } return None; } for j in 2..n{ ans[0][j]=1; } ans[n-2][0]=1; ans[n-1][1]=1; let mut p=P::new(0,0); let mut path=vec![p]; for t in 1..z.len(){ if t%2==0{ p+=DD[3]; } else{ p+=DD[2]; } path.push(p); } for &p in &path{ let sum=p.i+p.j; let mut xor=0; for i in 0..=sum{ let j=sum-i; if ibool{ *self>a && { *self=a; true } } fn chmax(&mut self,a:Self)->bool{ *self ChangeMinMax for T{} // library: https://github.com/rhoo19937/cp-lib // LURD const DD:[P;4]=[P{i:0,j:!0},P{i:!0,j:0},P{i:0,j:1},P{i:1,j:0}]; const DX:[P;8]=[P{i:0,j:!0},P{i:!0,j:!0},P{i:!0,j:0},P{i:!0,j:1},P{i:0,j:1},P{i:1,j:1},P{i:1,j:0},P{i:1,j:!0}]; #[derive(Clone,Copy,PartialEq,Eq,PartialOrd,Ord,Hash,Default)] struct P{ i:usize, j:usize, } impl P{ fn new(i:usize,j:usize)->P{ P{i,j} } fn in_range(self,h:usize,w:usize)->bool{ self.iusize{ self.i*w+self.j } fn from(id:usize,w:usize)->P{ P::new(id/w,id%w) } fn manh(self,p:P)->usize{ let abs_diff=|a,b|(a as i64-b as i64).abs() as usize; abs_diff(self.i,p.i)+abs_diff(self.j,p.j) } fn dir(self,p:P)->usize{ if self.i==p.i{ if self.j-1==p.j{ 0 } else{ assert!(self.j+1==p.j); 2 } } else{ if self.i-1==p.i{ 1 } else{ assert!(self.i+1==p.i); 3 } } } } impl std::fmt::Debug for P{ fn fmt(&self,f:&mut std::fmt::Formatter)->std::fmt::Result{ write!(f,"({}, {})",self.i,self.j) } } impl std::ops::Add for P{ type Output=P; fn add(self,a:P)->P{ P{ i:self.i+a.i, j:self.j+a.j, } } } impl std::ops::Sub for P{ type Output=P; fn sub(self,a:P)->P{ P{ i:self.i-a.i, j:self.j-a.j, } } } impl std::ops::Mul for P{ type Output=P; fn mul(self,a:usize)->P{ P{ i:self.i*a, j:self.j*a, } } } impl std::ops::Div for P{ type Output=P; fn div(self,a:usize)->P{ P{ i:self.i/a, j:self.j/a, } } } impl std::ops::Neg for P{ type Output=P; fn neg(self)->P{ P{ i:self.i.wrapping_neg(), j:self.j.wrapping_neg(), } } } macro_rules! impl_p_ops{ ($t:ty,$assign_trait:ident,$assign_func:ident,$op:tt)=>{ impl std::ops::$assign_trait<$t> for P{ fn $assign_func(&mut self,a:$t){ *self=*self $ op a; } } } } impl_p_ops!(P,AddAssign,add_assign,+); impl_p_ops!(P,SubAssign,sub_assign,-); impl_p_ops!(usize,MulAssign,mul_assign,*); impl_p_ops!(usize,DivAssign,div_assign,/); macro_rules! impl_p_index{ ($t:ty)=>{ impl> std::ops::Index

for $t{ type Output=T::Output; fn index(&self,idx:P)->&T::Output{ &self[idx.i][idx.j] } } impl> std::ops::IndexMut

for $t{ fn index_mut(&mut self,idx:P)->&mut T::Output{ &mut self[idx.i][idx.j] } } } } impl_p_index!([T]); impl_p_index!(Vec); fn iterp(h:usize,w:usize)->impl Iterator{ (0..h).map(move|i|(0..w).map(move|j|P::new(i,j))).flatten() } #[allow(unused)] mod rnd{ static mut X2:u32=12345; static mut X3:u32=0xcafef00d; static mut C_X1:u64=0xd15ea5e5<<32|23456; pub fn set_seed(seed:u64){ unsafe{ C_X1^=seed as u64; } } pub fn next()->u32{ unsafe{ let x=X3 as u64*3487286589; let ret=(X3^X2)+(C_X1 as u32^(x>>32) as u32); X3=X2; X2=C_X1 as u32; C_X1=x+(C_X1>>32); ret } } pub fn next64()->u64{ (next() as u64)<<32|next() as u64 } pub fn nextf()->f64{ f64::from_bits(0x3ff0000000000000|(next() as u64)<<20)-1. } pub fn get(n:usize)->usize{ assert!(0>32 } pub fn range(a:usize,b:usize)->usize{ assert!(ausize{ assert!(a<=skip && skipi64{ assert!(a(a:&mut [T]){ for i in (1..a.len()).rev(){ a.swap(i,get(i+1)); } } pub fn shuffle_iter(a:&mut [T])->impl Iterator{ (0..a.len()).rev().map(|i|{ a.swap(i,get(i+1)); a[i] }) } } #[allow(unused)] trait RandomChoice{ type Output; fn choice(&self)->&Self::Output; } impl RandomChoice for [T]{ type Output=T; fn choice(&self)->&T{ &self[rnd::get(self.len())] } } #[cfg(feature="local")] include!(concat!(env!("HOME"), "/cp/lib/debug_mod.rs")); #[cfg(not(feature="local"))] #[macro_export]macro_rules! debug{($($t:tt)*)=>{}} fn bit_iter(mut n:usize)->impl Iterator{ std::iter::from_fn(move||{ if n==0{ return None; } let i=n.trailing_zeros() as usize; n^=1<