AT_ndpc2026_h コイン拾い

縦横 $ N $ マスのグリッドがあります。グリッドの上から $ i $ 行目、左から $ j $ 列目のマスを $ (i,j) $ と呼びます。 グリッドの各マスの状態は $ N $ 個の長さ $ N $ の文字列 $ S_1,S_2,\dots,S_N $ によって表されます。 $ S_i $ の $ j $ 文字目が `@` である時は $ (i,j) $ はコインが $ 1 $ 枚落ちているマス、`.` である時は何もないマスです。 あなたはグリッドの $ (1,1) $ にいます。 $ (1,1) $ は何もないマスであることが保証されています。 あなたは以下の行動を $ 0 $ 回以上自由な回数行うことができます。 - 今自分がいるマスを $ (i,j) $ とする。右のマスまたは下のマス、すなわち $ (i,j+1) $ または $ (i+1,j) $ に移動する。グリッドの外への移動はできない。移動した先のマスにコインが落ちていた場合、あなたはそれを必ず拾う。 $ x = 0, 1, \dots, 2N-2 $ について次の問題を解いてください。 - あなたは $ 0 $ 回以上行動してあるマス $ (i,j) $ にたどり着きました。この時、あなたはコインを $ x $ 枚持っていました。 $ (i,j) $ としてあり得るマスは何マスありますか？

入力は以下の形式で標準入力から与えられる。 > $ N $ $ S_1 $ $ S_2 $ $ \vdots $ $ S_N $

$ 2N-1 $ 行出力せよ。 $ i $ 行目には $ x=i-1 $ の時の答えを出力せよ。

### 部分点 この問題には部分点が設定されている。 - $ N \leq 1500 $ であるデータセットに正解した場合、 $ 2 $ 点が与えられる。 ### Sample Explanation 1 例えば $ x=0 $ のとき、 $ (i,j) $ としてあり得るのは $ (1,1),(2,1),(2,2),(3,2),(3,3) $ の $ 5 $ 個です。 ### Constraints - $ 2 \leq N \leq 4000 $ - $ S_1, S_2, \dots, S_N $ は `@` と `.` からなる長さ $ N $ の文字列 - $ S_1 $ の $ 1 $ 文字目は `.` - $ N $ は整数