問題文

整数を係数とする多項式から成る列 $(A_0, A_1, \dots, A_{2^n - 1}), (B_0, B_1, \dots, B_{2^n - 1})$ が与えられます。 $$C_k := \left( \sum_{i \oplus j = k} A_i B_j \right) \bmod 2$$ で定義される列 $(C_0, C_1, \dots, C_{2^n - 1})$ を計算してください。 ただし $\oplus$ は bitwise xor を表します。

補足

整数を bit の列と解釈して $\bmod 2$ での畳み込みを行ったものを高速に計算する命令を、少なくとも yukicoder の C++ (GCC) において使用することができます。 Rust にも同種の命令が存在するようです。

#pragma GCC target("pclmul", "sse2", "sse4.1")
#include <emmintrin.h>
#include <smmintrin.h>
#include <wmmintrin.h>

__int64_t clmul(__int64_t x, __int64_t y) {
  __m128i x_ = _mm_set_epi64x(0, x);
  __m128i y_ = _mm_set_epi64x(0, y);
  __m128i z_ = _mm_clmulepi64_si128(x_, y_, 0);
  return _mm_extract_epi64(z_, 0);
}

/*

0 <= x, y < 2**32 のとき以下のコードと同じ結果になります。

__int64_t clmul(__int64_t x, __int64_t y) {
  __int64_t z = 0;
  for (int i = 0; i < 32; i++) {
    if (y >> i & 1) {
      z ^= x << i;
    }
  }
  return z;
}

*/

入力

$n$
$a_{0, 0}~a_{0, 1}~\dots~a_{0, 31}$
$a_{1, 0}~a_{1, 1}~\dots~a_{1, 31}$
$\vdots$
$a_{2^n-1, 0}~a_{2^n-1, 1}~\dots~a_{2^n-1, 31}$
$b_{0, 0}~b_{0, 1}~\dots~b_{0, 31}$
$b_{1, 0}~b_{1, 1}~\dots~b_{1, 31}$
$\vdots$
$b_{2^n-1, 0}~b_{2^n-1, 1}~\dots~b_{2^n-1, 31}$

この入力は $\displaystyle A_i = \sum_{j=0}^{31}a_{i, j} x^j$ であることを表します。 $B$ についても同様です。

入力制約

• $0 \leq n \leq 17$
• $0 \leq a_{i, j} \lt 2$
• $0 \leq b_{i, j} \lt 2$

出力

$c_{0, 0}~c_{0, 1}~\dots~c_{0, 62}$
$c_{1, 0}~c_{1, 1}~\dots~c_{1, 62}$
$\vdots$
$c_{2^n-1, 0}~c_{2^n-1, 1}~\dots~c_{2^n-1, 62}$

$\displaystyle C_i = \sum_{j=0}^{62}c_{i,j}x^j$ を満たす $c_{i,j}$ を出力してください。 最後に改行してください。

出力制約

• $0 \leq c_{i, j} \lt 2$

サンプル

0
1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

1
1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

3
1 0 1 0 1 1 1 1 0 0 0 1 1 0 0 1 1 1 1 1 1 0 0 0 1 1 0 1 0 1 0 0
0 0 1 1 0 1 0 1 1 0 0 1 1 0 0 1 1 1 0 1 0 0 0 0 1 1 1 1 1 1 1 1
1 0 0 1 1 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 0 1 0 0 1 0 0 0 1
1 1 1 1 1 1 1 1 1 0 0 0 1 0 1 0 1 1 0 0 1 0 1 1 0 0 0 0 0 1 1 1
0 0 0 1 1 0 1 0 1 1 0 0 0 0 1 0 0 0 1 1 1 0 1 1 0 0 1 0 0 0 0 1
0 1 0 0 1 1 0 0 1 1 0 0 0 0 0 1 0 1 0 1 0 0 0 0 1 0 1 0 1 0 1 1
0 1 1 0 1 0 1 0 1 0 1 1 1 0 1 1 0 1 0 0 0 0 1 1 0 1 0 1 0 0 1 1
0 0 0 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 1 0 1 0 0 0 1 0
1 1 1 0 0 1 0 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1
1 1 0 1 0 1 0 0 1 0 1 0 1 1 1 1 1 1 0 1 1 1 0 1 0 0 1 1 1 0 1 0
1 0 1 0 1 0 0 0 1 1 0 1 1 0 0 1 1 0 0 1 0 0 0 0 1 0 1 1 0 1 0 1
0 0 1 1 0 0 1 1 0 1 0 0 1 1 1 0 1 1 1 1 1 0 1 0 0 0 0 1 1 0 1 1
0 0 0 1 0 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 0 1 1 0 0 1 0 1 1 1 0 1
1 0 1 0 0 1 0 0 0 1 1 0 1 1 1 1 0 1 0 0 0 1 0 0 1 1 1 0 1 0 0 1
1 0 1 0 0 1 1 0 0 1 0 0 0 1 0 1 0 1 0 1 1 1 1 1 0 0 0 1 1 0 1 1
1 1 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 1 0 0 1 1 1 1 0 1 1 0 1 0 0 0

0 1 0 1 0 0 0 1 0 1 0 1 1 1 1 0 0 1 0 1 0 1 0 0 1 1 0 1 1 0 0 0 1 1 1 1 1 1 1 0 0 1 0 0 1 0 1 0 1 0 0 1 0 0 1 0 1 0 0 0 1 0 1
0 1 1 0 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 1 0 1 0 0 1 1 0 1 0 0 1 1 0 1 1 1 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 1 1 1 1 0 1 0 1 1 1 1 1
1 0 0 0 1 0 0 1 1 1 0 0 0 1 0 0 0 0 1 0 1 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 0 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 1 0 0
0 1 0 0 0 0 1 0 1 1 0 1 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 0 0 0 1 1 0 1 0 1 1 1 1 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 1 1 1 0 1 1 1 1 0
0 0 0 1 1 1 0 0 0 1 0 0 1 1 1 1 0 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 1 0 1 0 0 0 0 1 1 0 1 1 0 1 1 1 1 1 0 1 1 0 1 0 1 1 0
1 1 1 1 1 0 1 1 1 1 1 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0 1 1 1 1 0 1 0 0 1 0 0 0 0 0 0 0 1 1 1 1 1 1 0 1 0 0 1 0 1 0 0 0 1 0 0 0 0
0 0 1 0 1 0 1 0 0 0 1 0 1 1 1 0 0 0 0 1 1 0 1 1 0 0 0 1 0 0 0 1 0 0 1 0 1 1 1 0 1 1 1 0 0 0 1 0 1 0 0 0 0 0 0 1 1 1 1 0 0 0 1
0 1 1 1 0 0 1 0 0 1 1 1 1 0 0 0 0 0 0 1 1 0 1 1 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 1 0 1 1 1 0 1 1 0 1 1 1 0 0 0 0 1 0 0 0 1 1