AT_c_league2026_2_a Slide into Place

There is an $ N\times N $ grid. Let $ (0,0) $ be the coordinates of the top-left cell, and let $ (i,j) $ be the coordinates of the cell located $ i $ cells downward and $ j $ cells to the right from there. Initially, all cells are empty. Each cell is designated as either a target cell, where you want to place a piece, or a non-target cell. You may perform the following operation at most $ N^2 $ times. Choose one of the four sides of the grid and a corresponding row or column, and insert one piece from outside the grid. The first cell the piece enters is called the entrance. The entrance and the direction of movement for each side are as follows. Side Row or column Entrance Direction of movement Left Row $ i $ $ (i,0) $ Right Right Row $ i $ $ (i,N-1) $ Left Top Column $ j $ $ (0,j) $ Down Bottom Column $ j $ $ (N-1,j) $ Up An operation is not allowed if the entrance already contains a piece. The inserted piece moves straight from the entrance in the specified direction until the next cell already contains a piece or is outside the grid, at which point it stops in its current cell and remains fixed there. A piece in a cell adjacent to the side of its path does not cause it to stop. A fixed piece cannot be moved or removed. Each operation finishes before the next operation begins. Find a sequence of operations that achieves as high a score as possible by placing more pieces in target cells while limiting the number of pieces in non-target cells. #### Example Operations The following example uses an $ N=4 $ grid for illustration. In the actual input, $ N=30 $ . Light blue cells are target cells, green pieces are in target cells, and red pieces are in non-target cells. In the figure, $ t $ is the number of operations performed, the numbers on the pieces indicate their insertion order, and the purple arrow and ring show the path and stopping position of the most recently inserted piece. The initial grid and the grid after each of three operations 1. Insert a piece into row $ 1 $ from the left. It stops at $ (1,3) $ , at the edge of the grid. 2. Insert a piece into column $ 2 $ from the top. It stops at $ (3,2) $ . It passes beside the piece at $ (1,3) $ without stopping. 3. Insert a piece into column $ 3 $ from the bottom. It stops at $ (2,3) $ , just before the piece at $ (1,3) $ . After these operations, you cannot insert a piece into row $ 1 $ from the right because the entrance $ (1,3) $ already contains a piece.

Input is given from Standard Input in the following format. > $ N $ $ s_0 $ $ \vdots $ $ s_{N-1} $ Each value satisfies the following constraints. - $ N=30 $ - $ s_i $ is a string of length $ N $ consisting of `o` and `.`. The $ j $ -th character of $ s_i $ indicates whether cell $ (i,j) $ is a target cell: `o` denotes a target cell, and `.` denotes a non-target cell. Character positions in each string are also indexed from $ 0 $ .

Output to Standard Output in the following format. > $ d_0 $ $ k_0 $ $ \vdots $ $ d_{K-1} $ $ k_{K-1} $ Here, $ K $ is the number of operations you output and must be at most $ N^2 $ . For each $ t=0,\ldots,K-1 $ , $ d_t $ and $ k_t $ are integers specifying the $ t $ -th operation and must satisfy $ 0\leq d_t\leq 3 $ and $ 0\leq k_t

### Scoring After all operations, let $ E $ be the number of target cells without a piece, and let $ B $ be the number of pieces in non-target cells. You receive the following score. \\\[ S=N^2-E-B+1 \\\] After the three operations in the example above, $ E=2 $ and $ B=1 $ , so the score is $ 4^2-2-1+1=14 $ . There are 100 test cases, and the score of a submission is the sum of the scores for all test cases. If your submission produces an illegal output or exceeds the time limit for some test cases, the submission itself will be judged as WA or TLE , and the score of the submission will be zero. The highest score obtained during the contest will determine the final ranking, and there will be no system test after the contest. If more than one participant gets the same score, they will be ranked in the same place regardless of the submission time. ### Input Generation Set $ N=30 $ . Choose a real number $ p $ uniformly at random from the interval $ [0.35,0.65] $ . Independently for each cell, designate it as a target cell with probability $ p $ and as a non-target cell otherwise. ### Tools (Input generator and visualizer) - [Web version](https://img.atcoder.jp/c-league2026-2/RqpYgVXL.html?lang=en): This is more powerful than the local version providing animations and manual play. - [Local version](https://img.atcoder.jp/c-league2026-2/RqpYgVXL.zip): You need a compilation environment of [Rust language](https://www.rust-lang.org/). If it does not compile, please try `rustup update`. - [Pre-compiled binary for Windows](https://img.atcoder.jp/c-league2026-2/RqpYgVXL_windows.zip): If you are not familiar with the Rust language environment, please use this instead. Please be aware that sharing visualization results or discussing solutions/ideas with anyone outside your team during the contest is prohibited.