Story

The Country of yukicoder is a land rich in nature, with a vast forest.

One day, mech_39, who manages the forest, had a prophetic dream. In the dream, lightning would strike somewhere in the forest tomorrow and start a forest fire. Given the season, if lightning strikes a dry tree, the fire is expected to spread and become large-scale.

So, to protect the forest, mech_39 decided to cut down some trees today to prevent the fire from spreading. However, cutting down too many trees would defeat the purpose.

Cut down a limited number of trees to minimize the expected number of trees burned.

Problem Statement

There is a forest consisting of an $N \times N$ grid. The cell in the $i$-th row from the top and the $j$-th column from the left is denoted by $(i, j)$ $(0 \leq i, j < N)$. Each cell is assigned an integer $d_{i,j}$ between $0$ and $9$, inclusive. A cell with $d_{i,j} = 0$ is a lake or a river and has no tree. A cell with $d_{i,j} \geq 1$ has $1$ tree, and $d_{i,j}$ represents the dryness level of that tree.

Tomorrow, a forest fire will occur as follows.

1. Each tree independently becomes dry with probability $d_{i,j} / 10$, and otherwise becomes wet.
2. Lightning strikes $1$ cell chosen uniformly at random from the $N^2$ cells.
3. If the lightning strikes a dry tree, that tree burns, and the fire spreads successively to dry trees adjacent vertically or horizontally. The fire does not spread to wet trees or cells without trees.

Today, you may cut down at most $K$ trees. A cell whose tree has been cut down becomes a cell without a tree, and it neither burns nor transmits fire.

Choose the trees to cut down so that the expected number $E$ of burned trees is as small as possible.

Scoring

Let $E_0$ be the expected number of burned trees when no trees are cut down. You obtain the following score. A higher score is better. $$\mathrm{round}\left(10^6 \times \left(1 + \log_2 \frac{E_0}{E}\right)\right)$$

Notes

Let $C_1, C_2, \ldots$ be the 4-neighbor connected components of dry trees that have not been cut down. The probability that lightning strikes component $C_k$ is $|C_k| / N^2$, in which case $|C_k|$ trees burn, so $$E = \mathbb{E}\left[\frac{1}{N^2} \sum_{k} |C_k|^2\right]$$ holds.

Since computing $E$ and $E_0$ exactly is difficult, the judge samples the dryness states independently $40000$ times, computes the expectation in the formula above for each sample both with and without cutting, and approximates $E$ and $E_0$ by the averages (since the same samples are shared, $E = E_0$ always holds if no trees are cut down). The random seed is fixed for each input, so the same output always receives the same score.

There are $50$ test cases, and the sum of the scores of the test cases is the score of the submission. If a submission produces an invalid output or exceeds the time limit on one or more test cases, the score of the submission is $0$ points. The final ranking is determined by the highest score obtained during the contest, and no system test is performed after the contest ends.

Input

$N$ $K$
$d_{0,0}d_{0,1}...d_{0,N-1}$
$\vdots$
$d_{N-1,0}d_{N-1,1}...d_{N-1,N-1}$

• $N$ represents the size of the forest, and $N=50$.
• $K$ is the upper limit on the number of trees that can be cut down, and $K=100$.
• $d_{i,j}$ is an integer representing the presence or absence of a tree at $(i,j)$ and the dryness level of the tree, and satisfies $0 \leq d_{i,j} \leq 9$.

Output

Let $M$ $(0 \leq M \leq K)$ be the number of trees to cut down, and let $(i_0, j_0), \ldots, (i_{M-1}, j_{M-1})$ be the cells of the trees to cut down. Output in the following format. Each $(i_k, j_k)$ must be a distinct cell satisfying $d_{i_k, j_k} \geq 1$.

Added at 15:17: Cutting down a cell that is not a tree results in WA. There is no problem with the behavior of the visualizer or the tester.

$M$
$i_0 \quad j_0$
$\vdots$
$i_{M-1} \quad j_{M-1}$

Sample

50 100
66656634224434333444323423443888987978788777977999
66444624423232242224232424243989887988877987979878
56564642242234324342234344343999899789789798778898
65666463343422424322243344432999999888789789899778
55545464242234332224244422244899988999778878799998
44544444343342444434434334223998889999978977877988
06454562232442333332243333232999899998899897777977
04456659344423232342323224243988999898898778889779
00656659343334424422344332423989999998898777787887
40556569842444243234433344224298999998999888779778
60445589992442332433322322244299899998998899899897
60000599989223332334222332444488899999998889877877
54640599899932322342332223242288999898999897778788
65440099999992422443232223422299998898989878898979
55654009999893234332333222324453544344334497889978
45465098898999423432432433422993344555443588897977
45569000889999844424234434399995333534454359889898
45569990099899892233324242999989335345545339877889
55459900899899888333333488989989335334355537989799
55558909999999999932338888989985545354534378697889
55589809889988999993499999889955668767777666666768
64599808988999989999899999999665558866876678868887
44599800989999998981399989996755566778866766866678
64898890998998989992221899876767664768786777666788
45999900999898999833121238555557544587667767768788
55899909999898997791333331565555466648678688786886
59999808989997879873222221676764666566778677766786
59999900998887798799333211675746455565777876668676
58999900977988797799731337766655456556687768766868
99999800997789797989921775756554654665686667678777
99998980007888999897986757766565644465546686898787
99899453008007777899986775777775456446457889988987
99335535030000097897878667575764445656588989778779
63453345000000008787778877676654554546577877899978
77554433500000008878668876566577455577598789987779
76534334400000009797866667855557755765689989778979
75565543400000009888677878687656576675777987898879
77655444300000009878866768877675676576689787779877
77665755530000037766686778878675665677679789998788
76766668666888883988688886788856555567667988998988
67757558687886788776867678676876657656758989988988
87567565677878677667676686868855567776777898879888
77655667656787687766768787778667787677678888999899
67565756655777787886878776788867776768676879988899
66556755577557766887686667798987687687877899899898
86657577565776568868687689989966777688767699989989
77565666556667675886678998889868677867766789998998
88777657776775765578789888888677688687887899988999
87667665555566775686898899997575868877788689998899
77675575776566576689999989955567787687777888999888

3
0 32
1 33
2 34

Input Generation

$\mathrm{rand}(L, U)$ is a function that generates a uniformly random integer between $L$ and $U$, inclusive, and $\mathrm{randf}(L, U)$ is a function that generates a uniformly random real number at least $L$ and less than $U$.

$\bold{乾燥度の生成}$
Place $30$ points $p_1, \ldots, p_{30}$. The coordinates $(y_k, x_k)$ of each point are $y_k = \mathrm{randf}(0, 50)$, $x_k = \mathrm{randf}(0, 50)$. The sequence of values "$1$ each of $2, 3$, $2$ each of $4, 5$, and $6$ each of $6, 7, 8, 9$" ($30$ values in total) is randomly shuffled and assigned to $p_1, \ldots, p_{30}$.

For each cell $(i, j)$, take the value of the point $p_k$ with the smallest Euclidean distance from the point $(i + 0.5, j + 0.5)$ (if multiple points are at the same distance, the one with the smallest $k$), add $\mathrm{rand}(-1, 1)$ to it, clamp it to between $1$ and $9$, inclusive, and let the result be $d_{i,j}$.

$\bold{湖の生成}$
Create $\mathrm{rand}(1, 4)$ lakes. For each lake, choose the center coordinates $(y, x)$ as $y = \mathrm{randf}(0, 50)$, $x = \mathrm{randf}(0, 50)$ and the radius $r$ as $\mathrm{randf}(2, 5)$, and overwrite with $d_{i,j} = 0$ the cells for which the Euclidean distance between the point $(i + 0.5, j + 0.5)$ and the center is less than $r$.

$\bold{川の生成}$
Create $\mathrm{rand}(0, 2)$ rivers. Each river chooses $1$ lake uniformly at random and flows out from the cell containing its center. Choose the flow direction $v$ uniformly at random from up, down, left, and right, and repeat the following until going outside the board.

• Overwrite the current cell $(i, j)$ with $d_{i,j} = 0$.
• Advance $1$ cell: in the direction $v$ with probability $1/2$, and in each of the directions obtained by rotating $v$ by $90$ degrees to the left or right with probability $1/4$.

Tools (Input Generator and Visualizer)

• Web visualizer: You can generate inputs, compute scores, and visualize outputs.
• Local version: A Rust compilation environment is required to use it. See the included README for usage.

Use of Generative AI

The use of generative AI follows AtCoder's AHC GenAI Rules Trial Contest 2026. Be sure to include the specified prompt.

Briefly, using generative AI to devise solutions is prohibited, but delegating only the implementation to it is allowed.