AT_ndpc2026_h コイン拾い

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?

The input is given from standard input in the following format: > $ N $ $ S_1 $ $ S_2 $ $ \vdots $ $ S_N $

Print $ 2N-1 $ lines. On the $ i $ -th line, output the answer for $ 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 Explanation 1 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