マルチテストについての説明はこちら (サンプル問題を確認されていない方のみお読みください。)


配点:100100

問題文

以下の事柄を定めます:

  • char(0)\mathrm{char}(0) \coloneqq 0,char(1), \,\mathrm{char}(1) \coloneqq 1
  • 文字列 ss に対して s[k]s[k]ssk(1kS)k \scriptsize \; (1 \leq k \leq |S|) 番目の文字.
  • 文字列 ss に対して rev(s)\mathrm{rev}(s)ss を逆順にした文字列.
  • 22 文字列 s,ts, t に対して s+ts + ts,ts, t をこの順に連結した文字列.
  • x<2nx < 2^n なる 22 非負整数 n,xn, x に対して binn(x)\mathrm{bin}_n(x)xxnn 桁の 22 進数表現.
    • より厳密には,binn(x)\mathrm{bin}_n(x) は長さ nn の文字列であって以下の条件を満たすもの:
      • 1kn1 \leq k \leq n なる任意の整数 kk について binn(x)[k]=char(x2nkmod2)\displaystyle \mathrm{bin}_n(x)[k] = \mathrm{char}\left(\left \lfloor \frac{x}{2^{n-k}} \right\rfloor \bmod 2 \right ) である.
    • たとえば bin8(6)=\mathrm{bin}_8(6) = 00000110

NN 個の非負整数 A1,A2,,ANA_1, A_2, \ldots, A_N があります.
ただし Ak<216(1kN)A_k < 2^{16} \scriptsize \; (1 \leq k \leq N) です.

ここで,文字列 SS を次のように定めます:

  • Srev(bin16(A1))+rev(bin16(A2))++rev(bin16(AN))S \coloneqq \mathrm{rev}(\mathrm{bin}_{16}(A_1)) + \mathrm{rev}(\mathrm{bin}_{16}(A_2)) + \cdots + \mathrm{rev}(\mathrm{bin}_{16}(A_{N}))

以下の条件をいずれも満たすような,長さ 2N2N の非負整数列 (B1,B2,,B2N)(B_1, B_2, \ldots, B_{2N}) を求めてください:

  • Bk<28(1k2N)B_k < 2^{8} \scriptsize \; (1 \leq k \leq 2N)
  • S=rev(bin8(B1))+rev(bin8(B2))++rev(bin8(B2N))S = \mathrm{rev}(\mathrm{bin}_8(B_1)) + \mathrm{rev}(\mathrm{bin}_8(B_2)) + \cdots + \mathrm{rev}(\mathrm{bin}_8(B_{2N}))

答えは必ず一つ存在します.

制約

  • 1Φ1051 \leq \Phi \leq 10^5
  • 1N1 \leq N
  • ϕΦϕ(N)105\sum_{\phi} \Phi_{\phi}(N) \leq 10^5
  • 0Ai<216(1iN)0 \leq A_i < 2^{16} \scriptsize \; (1 \leq i \leq N)
  • 入力はすべて整数

入力

各テストケースの入力は,それぞれ以下の形式で与えられる:

NN
A1A2ANA_1 \enspace A_2 \enspace \ldots \enspace A_N

出力

答えとなる列を,要素ごとに空白もしくは改行で区切って出力せよ.

サンプル

入力例1
1
2
10527 6715
出力例1
31 41 59 26

S=rev(S = \mathrm{rev}(0010100100011111)+rev() + \mathrm{rev}(0001101000111011)=) \\ = 11111000100101001101110001011000=rev( \\ = \mathrm{rev}(00011111)+rev() + \mathrm{rev}(00101001)+rev() + \mathrm{rev}(00111011)+rev() + \mathrm{rev}(00011010)) です.


入力例2
4
2
9982 44353
3
998 244 353
5
99 82 44 35 3
9
9 9 8 2 4 4 3 5 3
出力例2
254 38 65 173
230 3 244 0 97 1
99 0 82 0 44 0 35 0 3 0
9 0 9 0 8 0 2 0 4 0 4 0 3 0 5 0 3 0

提出


Go (1.21)