AT_past202309_k マス目

There is an $ N \times N $ grid. Let $ (i,j) $ denote the square at the $ i $ -th row from the top and $ j $ -th square from the left. Each square is one of the following: the starting point, a goal, a passage, and a hole. The state of the square $ (i,j) $ is given as $ S_{i,j} $ . - `S` indicates that the square is the starting point. There is exactly one starting point. - `G` indicates that the square is a goal. There is one or more goals. - `. ` indicates that the square is a passage. - `X` indicates that the square is a hole. Solve the following problem for $ k=1,2,\dots,N-1 $ . You are initially at the starting square. Then, you repeat the following operation. - Choose one of the four directions: up, down, left, right. Move $ k $ squares consecutively in the chosen direction. You may not pass through a hole square or exit the grid by the operation. Determine if you can be at a goal square at the end of an operation, and if so, find the minimum number of operations required to do so. Note that passing through a goal in the middle of an operation does not count as finishing at a goal square.

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

Print $ N-1 $ lines. For $ 1 \le i \le N-1 $ , the $ i $ -th line should contain the minimum number of operations required to be at a goal square at the end of an operation for $ k=i $ if it is possible to do so, and `-1` otherwise.

### Sample Explanation 1 For $ k=2 $ , you can perform two operations as follows to be at the goal square at the end of an operation. - Choose down. Move from $ (1,1) $ to $ (3,1) $ . - Choose right. Move from $ (3,1) $ to $ (3,3) $ . With just one operation, you cannot be at a goal square at the end of an operation, so the answer is $ 2 $ . Note that for $ k=3 $ , the operation cannot be performed as follows. - Choose right. Move from $ (1,1) $ to $ (1,4) $ . This operation is not allowed because it passes through $ (1,2) $ , which is a hole. ### Constraints - $ 1 \le N \le 1500 $ - $ S_{i,j} $ is `S`, `G`, `.`, or `X`. - There is exactly one pair $ (i,j) $ such that $ S_{i,j}= $ `S`. - There is one or more pairs $ (i,j) $ such that $ S_{i,j}= $ `G`. - $ N $ is an integer.