問題文

寝癖くんが昨夜通販サイトで注文したキーボードが今朝自宅に届けられました。

早速使ってみようと、ケーブルでキーボードとPCを繋げようとしますが、なぜか正しい向きで差し込もうとしても、ある確率で差し込みに失敗してしまいます。

寝癖くんは、コネクタの差し込みに失敗すると、ケーブルを $180^\circ$ 回転させて上下ひっくり返した状態で再度差し込みを試み、成功するまでこれを続けます。

ここで、$i$ 回目の差し込みが正しい差し込みであるとき、差し込みに成功する確率は $1-2^{-(i-1)}$ であり、そうでない差し込みのとき、差し込みに成功する確率は $0$ です。

ケーブル側およびPC側のコネクタの形状 $S$ と $T$ が $H \times W$ のグリッドで与えられます。

差し込みに成功するまでにかかる試行回数の期待値が存在する場合、その期待値を求めてください。

期待値が存在しない(無限大になる)場合は -1 と出力してください。

なお、$1$ 回目の差し込みでは $S$ と同じ向きで行うこととし、$H\times W$ のグリッドで表された2つのコネクタ形状 $S,T$ について $S_{i,j}=T_{i,j}$ を満たす組 $(i, j)\ (1 \le i \le H, 1 \le j \le W)$ が存在しない状態での差し込みを正しい差し込みといいます。

入力

$H\ W$
$S_{1,1}S_{1,2}\dots S_{1, W}$
$S_{2,1}S_{2,2}\dots S_{2, W}$
$\vdots$
$S_{H,1}S_{H,2}\dots S_{H, W}$
$T_{1,1}T_{1,2}\dots T_{1, W}$
$T_{2,1}T_{2,2}\dots T_{2, W}$
$\vdots$
$T_{H,1}T_{H,2}\dots T_{H, W}$

• $3 \le H, W \le 20$
• $S,T$ は # と . のみからなる
• $i\in\{1,H\}$ または $j\in\{1,W\}$ のとき$S_{i,j}=$ . かつ $T_{i,j}=$ #

出力

差し込みに成功するまでにかかる試行回数の期待値が存在する場合は、その期待値を一行で出力してください。また、存在しない場合は -1 を出力してください。

なお、想定回答との絶対誤差または相対誤差が$10^{-6}$以下であれば正解と判定されます。

サンプル

6 20
....................
.##################.
.#................#.
.##################.
.##################.
....................
####################
#..................#
#.################.#
#..................#
#..................#
####################

3.5317401904617327