AT_ahc050_a [AHC050A] Gamble on Ice

There is a skating rink consisting of an $ N \times N $ grid. The top-left cell has coordinates $ (0,0) $ , and a cell located $ i $ cells downward and $ j $ cells to the right has coordinates $ (i,j) $ . The area outside the $ N \times N $ grid is entirely covered by rocks and cannot be entered. Initially, $ M $ cells contain rocks. Using this skating rink and a single robot, you play the following game: - At the beginning of the game, your prize money is 0 yen. - First, you declare a sequence $ P = ( P_0,P_1,\dots,P_{N^2 - M - 1} ) $ , which is an arbitrary ordering of the $ N^2 - M $ rock-free cells. - Then, one of the rock-free cells is uniformly randomly selected, and the robot is placed there. - Afterwards, for $ i = 0,1,\dots,N^2 - M - 1 $ , the following is repeated: - First, the robot uniformly randomly selects one of the four directions: up, down, left, or right. - Then, the robot moves in that direction in a straight line until it hits a rock. - Note that the robot may not move at all. - After that, a rock is placed on cell $ P_i $ . - If the robot is on that cell, it is crushed and the game ends. - If the robot is not on that cell, you earn 1 yen. Find a sequence $ P $ that maximizes the expected value of the total prize money you can earn.

Input is given from Standard Input in the following format: > $ N $ $ M $ $ S_{0,0} \dots S_{0,N-1} $ $ \vdots $ $ S_{N-1,0} \dots S_{N-1,N-1} $ - In all test cases, $ N $ is fixed to $ 40 $ . - $ M $ is an integer between $ N^2/10 $ and $ N^2/4 $ , inclusive. - Each $ S_{i,0} \dots S_{i,N-1} $ is a string of $ N $ characters consisting of `#` and `.`, where `#` indicates that cell $ (i,j) $ initially contains a rock, and `.` indicates that cell $ (i,j) $ is initially rock-free.

Let the computed sequence $ P $ be represented as $ P_i=(x_i,y_i) $ . Output it to Standard Output in the following format: > $ x_0 $ $ y_0 $ $ \vdots $ $ x_{N^2 - M - 1} $ $ y_{N^2 - M - 1} $ The sequence $ P $ must satisfy the following constraints: - All $ P_i $ must be distinct. - For every $ P_i $ , the corresponding cell must be rock-free in the initial state. [Show example](https://img.atcoder.jp/ahc050/k1BmZE1o.html?lang=en&seed=0&output=sample)

### Scoring Let $ E $ be the expected value of the total prize money you can earn. Then, your score is $ \displaystyle {\rm round} \left ( \frac{10^6 \times E}{N^2 - M - 1} \right ) $ . There are $ 150 $ test cases, and the score of a submission is the total score for each test case. 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 - First, set $ N=40 $ . - Next, choose an integer $ M $ uniformly at random from the range $ N^2/10 $ to $ N^2/4 $ , inclusive. - Finally, select $ M $ distinct cells uniformly at random from the $ N^2 $ cells, and place rocks on those cells to determine the initial state of the grid. ### Tools (Input generator and visualizer) - [Web version](https://img.atcoder.jp/ahc050/k1BmZE1o.html?lang=en): This is more powerful than the local version providing animations and manual play. - [Local version](https://img.atcoder.jp/ahc050/k1BmZE1o.zip): You need a compilation environment of [Rust language](https://www.rust-lang.org/). - [Pre-compiled binary for Windows](https://img.atcoder.jp/ahc050/k1BmZE1o_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 during the contest is prohibited.