問題文

HHWW 列のマス目が与えられます。 マス目の状態は HH 個の長さ WW の文字列 S1,S2,...,SHS_1, S_2, ..., S_H で表されます。 Si,j=S_{i, j} = "#" ならば ii 行目 jj 列目のマスが黒く塗られていて、 Si,j=S_{i, j} = "." ならば ii 行目 jj 列目のマスが白く塗られていることを指します。

ここで、以下の条件を満たす盤面 SSKK 次市松模様と定義します。

  • 0x,y10100 \leq x, y \leq 10 ^ {10} について、xK+yK\lfloor \frac{x}{K} \rfloor + \lfloor \frac{y}{K} \rfloor が奇数ならば Tx,yT_{x, y} は黒く塗られていて、偶数ならば Tx,yT_{x, y} は白く塗られているとする
  • 1iH, 1jW1 \leq i \leq H, \ 1 \leq j \leq W を満たす任意の (i,j)(i, j) について、Si,jS_{i, j} = Ti+p,j+qT_{i+p, j+q} となる (p,q)(p, q) の組み合わせ (1p,qK)(1 \leq p, q \leq K) が存在する

SSKK 次市松模様であるとしたとき、条件を満たす最小の正整数 KK を出力してください。 条件を満たす KK が存在しないときは 1-1 を出力してください。

制約

  • 1H,W10001 \leq H, W \leq 1000

入力

入力は以下の形式で与えられます。

H    WS1,1S1,2...S1,WS2,1      ...S2,W   SH,1     ...SH,WH \;\; W\\ S_{1,1}S_{1,2}...S_{1,W}\\ S_{2,1} \ \ \ \ \ \ ... S_{2,W}\\ \ \ \ ⋮\\ S_{H,1} \ \ \ \ \ ... S_{H,W}\\

出力

計算結果を一行に出力せよ。

サンプル

入力1
3 3
.#.
#.#
.#.
出力1
1

与えられたマス目は 11 次市松模様です。

入力2
4 5
#..##
.##..
.##..
#..##
出力2
2

与えられたマス目は 22 次市松模様です。

入力3
4 5
#....
.####
.####
.####
出力3
4

考えられる市松模様のうち、最も KK が小さいものは 44 次市松模様です。

入力4
2 3
..#
.#.
出力4
-1

与えられたマス目は市松模様ではありません。

Submit


Go (1.21)