AT_ndpc2026_h.Coin

You are given an $N \times N$ grid. Let $(i,j)$ denote the cell in the $i$-th row from the top and the $j$-th column from the left.

The state of each cell is described by $N$ strings $S_1, S_2, \dots, S_N$, each of length $N$.
If the $j$-th character of $S_i$ is @, then cell $(i,j)$ contains one coin. If it is ., then the cell is empty.

You start at cell $(1,1)$. It is guaranteed that $(1,1)$ is empty.

You may perform the following action any number of times (including zero):

• Let your current position be $(i,j)$. Move to either the right cell $(i,j+1)$ or the down cell $(i+1,j)$. You cannot move outside the grid. If the destination cell contains a coin, you must pick it up.

For each $x = 0, 1, \dots, 2N-2$, solve the following:

• After performing some actions (possibly zero), you reach a cell $(i,j)$ while having exactly $x$ coins. How many possible cells $(i,j)$ are there?

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

每个格子的状态由 $N$ 个长度均为 $N$ 的字符串 $S_1, S_2, \dots, S_N$ 描述：
若 $S_i$ 的第 $j$ 个字符为 @，则格子 $(i,j)$ 中有一枚硬币；若为 .，则该格子为空。

你起始于格子 $(1,1)$，题目保证 $(1,1)$ 为空。

你可以执行以下操作任意多次（包括零次）：

• 设你当前位于格子 $(i,j)$，可移动至右侧格子 $(i,j+1)$ 或下方格子 $(i+1,j)$。你不能移出网格边界。若目标格子中含有一枚硬币，则你必须拾取它。

对每个 $x = 0, 1, \dots, 2N-2$，求解以下问题：

• 在执行若干次（可能为零次）操作后，你抵达某个格子 $(i,j)$，且此时恰好持有 $x$ 枚硬币。满足该条件的格子 $(i,j)$ 共有多少个？

The input is given from standard input in the following format:

$N$
$S_1$
$S_2$
$\vdots$
$S_N$

输入从标准输入中按以下格式给出：

$N$
$S_1$
$S_2$
$\vdots$
$S_N$

Print $2N-1$ lines. On the $i$-th line, output the answer for $x = i-1$.

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

Partial Score

This problem has partial scoring.

• If you solve the dataset with $N \leq 1500$, you will get $2$ points.

Sample 1 Explanation:
For example, when $x=0$, the possible cells $(i,j)$ are $(1,1), (2,1), (2,2), (3,2), (3,3)$, so there are $5$ such cells.

Constraints

• $2 \leq N \leq 4000$
• $S_1, S_2, \dots, S_N$ are strings of length $N$ consisting of @ and .
• The first character of $S_1$ is .
• $N$ is an integer

部分得分

本题采用部分得分制。

• 若你解决了满足 $N \leq 1500$ 的数据集，则可获得 $2$ 分。

样例 1 解释：
例如，当 $x=0$ 时，满足条件的格子 $(i,j)$ 有 $(1,1), (2,1), (2,2), (3,2), (3,3)$，共 $5$ 个。

约束条件

• $2 \leq N \leq 4000$
• $S_1, S_2, \dots, S_N$ 是由字符 @ 和 . 组成的长度为 $N$ 的字符串；
• $S_1$ 的第一个字符为 .；
• $N$ 是一个整数。