問題文

AtCoder社はブロックを組み合わせて指定されたシルエットの立体を作る知育玩具を開発している。 この玩具は $1\\times 1\\times 1$ の立方体を面同士で接合したポリキューブ状のブロックが複数と2次元の白黒シルエット画像2枚の組がセットになっている。 ブロックを組み合わせて一つの立体を作り、作った立体を正面から見た時のシルエットと、右側から見た時のシルエットが、シルエット画像に完全一致していたらゲームクリアである。

長く遊べるように、1セットのブロックに対して、シルエットの組を複数用意したい。 例えば左図の例にある6ブロックのセットからは、右図にあるようなシルエットの組2つが達成可能である。

玩具デザイナーであるあなたの仕事は、正面・右側のシルエットのペアが2組与えられるので、両方を作ることが出来るようなブロックのセットと、その作り方を求めることである。 小さなブロックは子供が誤って飲み込んでしまう可能性があるため、少数の大きなブロックのみからなるセットが望ましい。

パズルのルールについての補足

• ブロックは全て使い切らなくても良い(が、全て使い切るほうが良いスコアが得られる)。
• 各ブロックは $x$軸、$y$軸、$z$軸に対して90度単位で回転させることが出来るが反転させることは出来ない。
• ブロックの配置は各頂点が整数座標となるようにしなくてはならず、ブロック同士は正の体積の共通部分を持ってはならない。
• 作成する立体は連結でなくても良い。簡単のため、宙に浮かせるような配置も可能であるとする(追加で透明なブロックが大量にあり、自由に支えることが出来ると解釈せよ)。

シルエットについて

左から右方向に $x$ 軸、手前から奥方向に $y$ 軸、上から下方向に $z$ 軸を取る。 全てのブロックは $(0,0,0)$ と $(D,D,D)$ を対角とする立方体領域内に収まっているとする。 三次元の01配列 $b(x,y,z)$ を、$(x,y,z)$ と $(x+1,y+1,z+1)$ を対角とする単位立方体の領域をブロックが占めている場合に $b(x,y,z)=1$、そうでない場合に $b(x,y,z)=0$ と定義する。 このとき、前から見たシルエットは二次元の01配列 $f(z,x)$ であり、以下のように定義される。

\[ f(z,x)=\begin{cases} 1&(\sum_{y=0}^{D-1}b(x,y,z)\geq 1)\\ 0&(\sum_{y=0}^{D-1}b(x,y,z)=0) \end{cases} \]

同様に、右から見たシルエットは二次元の01配列 $r(z,y)$ であり、以下のように定義される。

\[ r(z,y)=\begin{cases} 1&(\sum_{x=0}^{D-1}b(x,y,z)\geq 1)\\ 0&(\sum_{x=0}^{D-1}b(x,y,z)=0) \end{cases} \]

得点

作成した玩具セットに含まれる各ブロックの体積を $v_1,\\cdots,v_n$ とする。 ここで、ブロックの体積とはそれを構成する $1\\times 1\\times 1$ の立方体の個数に等しい。 各ブロックは連結、すなわち構成するどの立方体同士も面を共有する立方体への移動によって到達可能でなければならない。 非連結なブロックが一つでもある場合は WA