AT_abc445_g [ABC445G] Knight Placement

There is a grid with $ N $ rows and $ N $ columns. The cell at the $ i $ -th row from the top $ (1 \le i \le N) $ and the $ j $ -th column from the left $ (1 \le j \le N) $ is called cell $ (i,j) $ . Each cell is an empty cell or a wall cell, represented by a sequence of $ N $ strings of length $ N $ each, $ (S_1,S_2,\ldots,S_N) $ . Cell $ (i,j)\ (1 \le i \le N,1 \le j \le N) $ is an empty cell if the $ j $ -th character of $ S_i $ is `.`, and a wall cell if it is `#`. You want to place as many pieces as possible on this grid. The placement of pieces is subject to the following constraints. - A piece cannot be placed on a wall cell. - At most one piece can be placed on a single cell. - If a piece is placed on cell $ (i,j) $ , no piece can be placed on the cell reached by moving $ A $ cells vertically and $ B $ cells horizontally from cell $ (i,j) $ , or the cell reached by moving $ B $ cells vertically and $ A $ cells horizontally. More formally, if a piece is placed on cell $ (i,j) $ , then no piece can be placed on any of cell $ (i+A,j+B), $ cell $ (i+B,j+A), $ cell $ (i+B,j-A), $ cell $ (i+A,j-B), $ cell $ (i-A,j-B), $ cell $ (i-B,j-A), $ cell $ (i-B,j+A), $ cell $ (i-A,j+B) $ (if those cells exist). Let $ K $ be the maximum number of pieces that can be placed under these constraints, and find one placement of $ K $ pieces satisfying the constraints.

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

Find one placement of $ K $ pieces satisfying the constraints, and output it as strings over $ N $ lines. The $ i $ -th line $ (1 \le i \le N) $ should contain a string of $ N $ characters consisting of `.`, `o`, and `#`. The $ j $ -th character $ (1 \le j \le N) $ of the string on the $ i $ -th line should be `.` if cell $ (i,j) $ is an empty cell with no piece, `o` if cell $ (i,j) $ is an empty cell with a piece, and `#` if cell $ (i,j) $ is a wall cell. If there are multiple valid placements, any of them will be accepted.

### Sample Explanation 1 For example, $ 10 $ pieces can be placed as follows while satisfying the constraints.  It is impossible to place $ 11 $ pieces while satisfying the constraints, so outputting the board corresponding to the placement above, ``` o.#.o oo##. o#..# ##.o# o#ooo ``` will be judged as correct. Note that any valid placement will be accepted if there are multiple of them. For example, the following also allows $ 10 $ pieces to be placed while satisfying the constraints.  Thus, outputting ``` oo#oo o.##o .#..# ##..# o#ooo ``` will also be judged as correct. ### Sample Explanation 2 The constraints can be satisfied by placing one piece on each empty cell. ### Constraints - $ 1 \le N \le 300 $ - $ 0 \le A \le B \le N $ - $ 1 \le B $ - $ N,A,B $ are integers. - $ S_i $ is a string of length $ N $ consisting of `.` and `#` $ (1 \le i \le N) $ .