配点 : $500$ 点

問題文

$xy$ -平面上のいくつかの点に村があります。 高橋君はこれらの村を民兵や魔女などの外敵から守るため、これらのすべての村を囲むようなお堀を建設します。

$0$ と $1$ からなる $4 \times 4$ 行列 $A = (A_{i, j})$ が与えられます。 $A_{i, j} = 1$ を満たす整数の組 $(i, j)$ $(1 \leq i, j \leq 4)$ ごとに、座標 $(i-0.5, j-0.5)$ に村があります。

お堀は平面上の多角形です。 高橋君は以下の条件をすべて満たすお堀を建設します（入力例１・出力例１の説明も参考にして下さい）。

1. 自己交差がない
2. 内部にすべての村を含む
3. すべての頂点の $x$ 座標と $y$ 座標は $0$ 以上 $4$ 以下の整数
4. すべての辺は $x$ 軸と $y$ 軸のどちらかに平行
5. それぞれの内角の大きさは $90$ 度または $270$ 度

高橋君が建設するお堀として考えられるものが何通りあるかを出力して下さい。

制約

• $A_{i, j} \in \lbrace 0, 1\rbrace$
• $A_{i, j} = 1$ となる $(i, j)$ が少なくとも $1$ つ存在する

入力

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

$A_{1, 1}$ $A_{1, 2}$ $A_{1, 3}$ $A_{1, 4}$

$A_{2, 1}$ $A_{2, 2}$ $A_{2, 3}$ $A_{2, 4}$

$A_{3, 1}$ $A_{3, 2}$ $A_{3, 3}$ $A_{3, 4}$

$A_{4, 1}$ $A_{4, 2}$ $A_{4, 3}$ $A_{4, 4}$

出力

高橋君が建設するお堀として考えられるものが何通りあるかを出力せよ。

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

1272

下記の $2$ つの画像の例は、高橋君が建設するお堀の条件を満たします。

下記の $4$ つの画像の例は、高橋君が建設するお堀の条件を満たしません。

上記の $4$ つの例が高橋君の建設するお堀の条件を満たさない理由は、以下の通りです。

• $1$ つ目の画像の例は、「自己交差がない」という条件を満たしません。
• $2$ つ目の画像の例は、「内部にすべての村を含む」という条件を満たしません。
• $3$ つ目の画像の例は、「すべての頂点の $x$ 座標と $y$ 座標は $0$ 以上 $4$ 以下の整数」という条件を満たしません。（座標が整数でない頂点があります。）
• $4$ つ目の画像の例は、「すべての辺は $x$ 軸と $y$ 軸のどちらかに平行」という条件を満たしません。

1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

1