use std::ops::*; #[derive(Clone, Copy)] struct Value(usize); impl Value { fn zero() -> Self { Value(0) } } impl Add for Value { type Output = Self; fn add(self, rhs: Self) -> Self::Output { Value(self.0 ^ rhs.0) } } impl Sub for Value { type Output = Self; fn sub(self, rhs: Self) -> Self::Output { Value(self.0 ^ rhs.0) } } impl Mul for Value { type Output = Self; fn mul(self, rhs: Self) -> Self::Output { Value(self.0 * rhs.0) /* use core::arch::x86_64::*; unsafe { let a = _mm_set_epi64x(0, self.0 as i64); let b = _mm_set_epi64x(0, rhs.0 as i64); let c = _mm_clmulepi64_si128(a, b, 0); Value(_mm_extract_epi64(c, 0) as usize) } */ } } // ---------- begin Scanner(require delimiter) ---------- mod scanner { pub struct Scanner { reader: R, buf: Vec, } #[allow(dead_code)] impl Scanner { pub fn new(reader: R) -> Self { Scanner { reader: reader, buf: Vec::with_capacity(1024), } } fn read(&mut self, del: u8) { self.buf.clear(); self.reader.read_until(del, &mut self.buf).ok(); assert!(self.buf.pop().unwrap() == del); } pub fn next(&mut self, del: u8) -> T { self.read(del); std::str::from_utf8(&self.buf) .unwrap() .trim() .parse::() .ok() .unwrap() } pub fn next_bytes(&mut self, del: u8) -> Vec { self.read(del); std::str::from_utf8(&self.buf) .unwrap() .trim() .bytes() .collect() } } } // ---------- end scanner(require delimiter) ---------- fn main() { let stdin = std::io::stdin(); let mut sc = scanner::Scanner::new(stdin.lock()); run(&mut sc); } fn run(sc: &mut scanner::Scanner) { let n: usize = sc.next(b'\n'); let mut a = vec![Value::zero(); 1 << n]; let mut b = vec![Value::zero(); 1 << n]; for a in a.iter_mut().chain(b.iter_mut()) { for i in 0..32 { let x = sc.next::(if i == 31 { b'\n' } else { b' ' }); a.0 |= x << i; } } let mut c = vec![Value::zero(); 1 << n]; rec(&mut c, &mut a, &mut b); use std::fmt::*; let mut s = String::new(); for c in c { for i in 0..63 { let p = c.0 >> i & 1; write!(&mut s, "{} ", p).ok(); } s.pop(); s.push('\n'); } print!("{}", s); } fn rec(c: &mut [Value], a: &mut [Value], b: &mut [Value]) { if c.len() <= 32 { for (i, a) in a.iter().enumerate() { for (j, b) in b.iter().enumerate() { c[i ^ j] = c[i ^ j] + *a * *b; } } return; } let m = c.len() / 2; let (al, ar) = a.split_at_mut(m); let (bl, br) = b.split_at_mut(m); let (cl, cr) = c.split_at_mut(m); rec(cl, al, bl); rec(cr, ar, br); let it = cl.iter_mut().zip(cr.iter_mut()); let it = it.zip(al.iter_mut().zip(ar.iter_mut())); let it = it.zip(bl.iter_mut().zip(br.iter_mut())); for (((cl, cr), (al, ar)), (bl, br)) in it { *cl = *cl + *cr; *cr = Value::zero(); *al = *al + *ar; *bl = *bl + *br; } rec(cr, al, bl); let it = cl.iter_mut().zip(cr.iter_mut()); let it = it.zip(al.iter_mut().zip(ar.iter_mut())); let it = it.zip(bl.iter_mut().zip(br.iter_mut())); for (((cl, cr), (al, ar)), (bl, br)) in it { *cr = *cr - *cl; *al = *al - *ar; *bl = *bl - *br; } }