#hitachi2020e. [hitachi2020_e]Odd Sum Rectangles

[hitachi2020_e]Odd Sum Rectangles

問題文

(2N1)(2^N - 1)(2M1)(2^M-1) 列のグリッドがあり、 あなたはこれからすべてのマスに 0,10, 1 のいずれかの数字を書き込みます。 上から ii 行目、左から jj 列目に書き込む数字を ai,ja_{i,j} とします。

$1\\leq i_1 \\leq i_2\\leq 2^N-1, 1\\leq j_1 \\leq j_2\\leq 2^M-1$ をみたす整数の組 (i1,i2,j1,j2)(i_1, i_2, j_1, j_2) に対し、 $S(i_1, i_2, j_1, j_2) = \\displaystyle \\sum_{r=i_1}^{i_2}\\sum_{c=j_1}^{j_2}a_{r,c}$ と定義し、 さらに、グリッドの「奇妙さ」を S(i1,i2,j1,j2)S(i_1, i_2, j_1, j_2) が奇数となるような (i1,i2,j1,j2)(i_1, i_2, j_1, j_2) の個数 と定義します。

奇妙さが最大となるような数字の書き込み方を 11 つ求めてください。

制約

  • N,MN, M11 以上 1010 以下の整数

入力

入力は以下の形式で標準入力から与えられる。

NN MM

出力

奇妙さが最大となる書き込み方の 11 つを、以下の形式で出力せよ。

a1,1a1,2cdotsa1,2M1a_{1,1}a_{1,2}\\cdots a_{1,2^M-1} a2,1a2,2cdotsa2,2M1a_{2,1}a_{2,2}\\cdots a_{2,2^M-1} vdots\\vdots a2N1,1a2N1,2cdotsa2N1,2M1a_{2^N-1,1}a_{2^N-1,2}\\cdots a_{2^N-1,2^M-1}


入力例 1

1 2

出力例 1

111

S(1,1,1,1)S(1, 1, 1, 1)S(1,1,2,2)S(1, 1, 2, 2)S(1,1,3,3)S(1, 1, 3, 3)S(1,1,1,3)S(1, 1, 1, 3) が奇数となるため、このグリッドの奇妙さは 44 です。

奇妙さを 55 以上にすることはできないため、これは奇妙さが最大となる書き込み方の 11 つです。