問題文

画面上で上から下へ落ちていくボールを左右に操作し、 障害物をよけて一番下を目指すコンピューターゲームがあります。

ゲーム画面は高さ $H$ マス、横 $W$ マスのグリッドで表されます。
上から $i$ 行目、左から $j$ 列目のマスを $(i,j)$ と表します。

ボールは時刻 $0$ に一番上の行のいずれかのマスにランダムに出現し、 $1$ 秒ごとに一つ下のマスに瞬間的に移動します。
つまり、 $t=1,2, \cdots ,H-1$ において、 時刻 $t$ に $(t,j)$ から $(t+1,j)$ に瞬間的に移動します。
また、 $(i,j)$ にボールがあるときにプレーヤーが左ボタンを押すと $(i,j-1)$ に、 右ボタンを押すと $(i,j+1)$ に瞬間的に移動します。
但し下への移動と左右への移動は同時にはできません（つまり斜め移動はできません）。 またグリッドの外には移動できません。

マス $(i,j)$ の障害物の有無は文字 $S_{i,j}$ で表されます。
$S_{i,j}=$#のときは障害物があり、.のときは障害物がありません。
ボールが障害物のあるマスに移動するとゲームオーバーです。
ゲームオーバーにならずに一番下の行のいずれかのマスに移動するとゲームクリアです。
一番上の行と一番下の行には障害物がありません。
また、ゲームクリア不可能な障害物配置になることはありません。

hamamuさんは腱鞘炎なので、 一秒間にボタンを押す回数の最大値 $P$ を最小化してゲームクリアしたいです。
形式的には、 $t=1,2, \cdots ,H-1$ において時刻 $t-1$ から $t$ の間にボタンを押す回数を $f(t)$ とし、 $$P=\max_{t=1,2,\cdots,H-1} f(t)$$ として、 $P$ を最小化したいです。
$k=1,2, \cdots ,W$ に対し、ボールがマス $(1,k)$ に出現したときの $P$ の最小値を求めてください。

制約

• $3 \le H \le 10^5$
• $1 \le W \le 10^5$
• $HW \le 5\times 10^5$
• $S_{1,j},S_{H,j} (1 \le j \le W)$は全て.
• 時刻 $0$ にボールがどのマスに出現しても、ゲームクリアが可能である
• $H,W$ は整数
• $S_{i,j}$ は.か#

入力

$H\ W$
$S_{1,1}S_{1,2} \cdots S_{1,W}$
$S_{2,1}S_{2,2} \cdots S_{2,W}$
$\cdots$
$S_{H,1}S_{H,2} \cdots S_{H,W}$

出力

$W$ 行出力してください。
$k$ 行目にボールがマス $(1,k)$ に出現したときの $P$ の最小値を出力してください。
最後に改行してください。

サンプル

3 3
...
##.
...

2
1
0

4 3
...
...
##.
...

1
1
0

5 8
........
.######.
........
##...###
........

2
2
2
3
3
3
3
3