题目描述

有一个 $N\times N$ 的网格。用 $(i,j)$ 表示从上往下第 $i$ 行、从左往右第 $j$ 列的方格。

第 $i$ 行的状态由字符串 $S_i$ 表示：

• 当 $S_{i,j}$ 为 @ 时，方格 $(i,j)$ 中有一枚硬币；
• 当 $S_{i,j}$ 为 . 时，方格 $(i,j)$ 中没有硬币。

保证起点 $(1,1)$ 中没有硬币。

你最初位于 $(1,1)$，手中没有硬币。每次可以向右或向下移动一格。到达一个含有硬币的方格时，必须捡起该硬币。

对于每个 $x=0,1,\ldots,2N-2$，求经过若干次移动后，恰好持有 $x$ 枚硬币时可能到达的方格数量。

限制条件

• $2\le N\le 4000$
• $S_i$ 是长度为 $N$、仅由 @ 与 . 组成的字符串。
• $S_{1,1}=\texttt{.}$
• $N$ 为整数。

部分分

• 对满足 $N\le 1500$ 的数据求解正确，可获得 $2$ 分。

输入

N
S_1
S_2
...
S_N

输出

输出 $2N-1$ 行。第 $i$ 行输出 $x=i-1$ 时的答案。

样例输入 1

3
.@@
..@
@..

样例输出 1

5
6
3
2
0

当 $x=0$ 时，可能到达的方格为

共 $5$ 个。

样例输入 2

7
...@@@.
..@@@@@
@...@..
..@..@.
.....@@
.@@@@@@
@@.@.@.

样例输出 2

15
29
28
23
19
13
6
5
3
0
0
0
0