#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include #include #include #include struct FacInt { int64_t p; uint32_t q; FacInt() = default; FacInt(int64_t p, uint32_t q) : p(p), q(q) {} FacInt(int64_t v) { if (v) { q = __builtin_ctzll(v); p = v >> q; } else { p = q = 0; } } friend FacInt operator-(const FacInt& x) { return FacInt{ -x.p, x.q }; } friend FacInt operator+(const FacInt& x, const FacInt& y) { if (x.p == 0) return y; if (y.p == 0) return x; uint32_t q = std::min(x.q, y.q); int64_t px = x.p << (x.q - q); int64_t py = y.p << (y.q - q); FacInt res = px + py; res.q += q; return res; } friend FacInt operator-(const FacInt& x, const FacInt& y) { return x + (-y); } friend FacInt operator*(const FacInt& x, const FacInt& y) { if (x.p == 0) return x; if (y.p == 0) return y; return FacInt{ x.p * y.p, x.q + y.q }; } friend FacInt operator/(const FacInt& x, const FacInt& y) { assert(y.p); if (x.p == 0) return x; assert(x.p % y.p == 0 and x.q >= y.q); return FacInt{ x.p / y.p, x.q - y.q }; } operator int64_t() { return p << q; } }; struct FacIntPoly : std::array { FacIntPoly() { for (std::size_t i = 0; i < 63; ++i) { (*this)[i] = FacInt{0}; } } friend FacIntPoly operator+(const FacIntPoly &x, const FacIntPoly &y) { FacIntPoly z; for (std::size_t i = 0; i < 63; ++i) { z[i] = x[i] + y[i]; } return z; } friend FacIntPoly operator-(const FacIntPoly &x, const FacIntPoly &y) { FacIntPoly z; for (std::size_t i = 0; i < 63; ++i) { z[i] = x[i] - y[i]; } return z; } friend FacIntPoly operator*(const FacIntPoly &x, const FacIntPoly &y) { FacIntPoly z; for (std::size_t i = 0; i < 32; ++i) for (std::size_t j = 0; j < 32; ++j) { z[i + j] = z[i + j] + x[i] * y[j]; } return z; } }; void unit_walsh_hadamard_transform(FacIntPoly& x0, FacIntPoly& x1) { FacIntPoly y0 = x0, y1 = x1; x0 = y0 + y1; // 1, 1 x1 = y0 - y1; // 1, -1 } template void unit_transform(UnitTransform transform, ReferenceGetter ref_getter, std::index_sequence) { transform(ref_getter(Seq)...); } void walsh_hadamard(std::vector& x) { const std::size_t n = x.size(); for (std::size_t block = 1; block < n; block *= 2) { for (std::size_t l = 0; l < n; l += 2 * block) { for (std::size_t offset = l; offset < l + block; ++offset) { const auto ref_getter = [&](std::size_t i) -> FacIntPoly& { return x[offset + i * block]; }; unit_transform(unit_walsh_hadamard_transform, ref_getter, std::make_index_sequence<2>()); } } } } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::size_t n; std::cin >> n; std::vector a(1 << n), b(1 << n), c(1 << n); for (std::size_t i = 0; i < 1U << n; ++i) { for (std::size_t j = 0; j < 32; ++j) { std::size_t bit; std::cin >> bit; a[i][j] = bit; } for (std::size_t j = 32; j < 63; ++j) { a[i][j] = 0; } } for (std::size_t i = 0; i < 1U << n; ++i) { for (std::size_t j = 0; j < 32; ++j) { std::size_t bit; std::cin >> bit; b[i][j] = bit; } for (std::size_t j = 32; j < 63; ++j) { b[i][j] = 0; } } walsh_hadamard(a); walsh_hadamard(b); for (std::size_t i = 0; i < 1U << n; ++i) { c[i] = a[i] * b[i]; } walsh_hadamard(c); for (std::size_t i = 0; i < 1U << n; ++i) { for (std::size_t j = 0; j < 63; ++j) { std::cout << (int64_t(c[i][j] / FacInt { 1, n }) & 1) << ' '; } std::cout << '\n'; } return 0; }