{"problem":{"name":"O. 1% Genius","description":{"content":"It's just another day at National Corps of Intelligence Services (NCIS), the country's biggest and most powerful espionage organization. You're enjoying your favorite drink as you read through some to","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10253O"},"statements":[{"statement_type":"Markdown","content":"It's just another day at National Corps of Intelligence Services (NCIS), the country's biggest and most powerful espionage organization. You're enjoying your favorite drink as you read through some top secret files and type away at your computer desk to finish your report for the previous mission. Everything seems normal, but then...\n\n\"No way, I'm getting hacked!\", your colleague suddenly exclaims.\n\n\"A port scan?\", you ask her.\n\n\"No. No, this is major. They've already burned through the NCIS public firewall,\" she replies, frantically typing at her keyboard.\n\n\"Well, isolate the node and dump it on the other side of the router,'' you suggest to her.\n\n\"I'm trying! It's moving too fast.\"\n\nAs she says this, you notice the hacker's progress on her screen. Multiple pictures of random cats keep on popping up. Several memes from Gag-Olympics show up. It looks like someone on Hacker Typer, but you are sure that this isn't a prank this time.\n\nNot being the type to just sit back and watch your precious colleague suffer, you heroically join her on the keyboard as she continues to type away to beat the hacker. Together, you can beat the hacker, you say.\n\nAs soon as you did this, more things popped up on the screen. CAPTCHAs? No, IQ tests! \"99% of the population can't solve this,\" it says on the screen.\n\n\"Which cup will be filled first?\"\n\nIt's a very tough and difficult logic puzzle where cups are connected via tubes, and water pours in from one of the cups. Thankfully, you always knew that you were part of that special 1% of the population that can solve this puzzle, and proceed to type with your colleague to beat the hacker. \n\nIn fact, instead of just knowing which cup will be filled first, you set yourself a more ambitious goal: to know precisely where the water is at any moment in time. But you're not willing to simulate the physics of flowing water accurately. Instead, you decide on the following approximation:\n\nWith these rules in place, you now wish to know which cells become water cells, and precisely when they turn into water cells. We denote the cell at row $i$ (from top to bottom) and column $j$ (from left to right) by $(i, j)$. If cell $(i, j)$ will eventually turn into a water cell, let $w (i, j)$ be the number of seconds since the beginning when that cell first turns into a water cell. (Note that $w (i, j) = 0$ for all cells $(i, j)$ that are initially water cells.) Your goal is to compute $w (i, j)$ for every cell $(i, j)$ that will eventually turn into a water cell.\n\nThe first line contains $t$, the number of test cases. The $t$ test cases follow.\n\nThe first line of each test case contains two space-separated integers $r$ and $c$ denoting the number of rows and columns of the puzzle grid. Each of the next $r$ lines contains a string of $c$ characters indicating a row of the initial grid. Each character is either _#_, _._ or _W_ with the following meanings:\n\n*Constraints*\n\n$1 <= t <= 10^4$ \n\n$1 <= r, c <= 150000$ \n\n$r c <= 1500000$ \n\nThe sum of the $r c$ in a single file is $<= 1500000$.\n\nThere is at least one _W_.\n\nAll _W_'s appear in the first row.\n\nNo solid cells appear in the first row.\n\nFor each test case, first print a single line containing the maximum $w (i, j)$ among all cells $(i, j)$ that will eventually turn into a water cell. Then print $r$ rows, each containing a string of $c$ characters. The $j$th character in the $i$th line is:\n\nThe following are the illustrations of the state of the first test case at various points in time:\n\n## Input\n\nThe first line contains $t$, the number of test cases. The $t$ test cases follow.The first line of each test case contains two space-separated integers $r$ and $c$ denoting the number of rows and columns of the puzzle grid. Each of the next $r$ lines contains a string of $c$ characters indicating a row of the initial grid. Each character is either _#_, _._ or _W_ with the following meanings:  _#_ denotes a solid cell;  _._ denotes an empty cell;  _W_ denotes a water cell. *Constraints*$1 <= t <= 10^4$ $1 <= r, c <= 150000$ $r c <= 1500000$ The sum of the $r c$ in a single file is $<= 1500000$.There is at least one _W_.All _W_'s appear in the first row.No solid cells appear in the first row.\n\n## Output\n\nFor each test case, first print a single line containing the maximum $w (i, j)$ among all cells $(i, j)$ that will eventually turn into a water cell. Then print $r$ rows, each containing a string of $c$ characters. The $j$th character in the $i$th line is:  _#_ if cell $(i, j)$ is a solid cell;  _._ if cell $(i, j)$ is an empty cell that will never turn into a water cell;  The last digit of $w (i, j)$ if cell $(i, j)$ will eventually turn into a water cell. \n\n[samples]\n\n## Note\n\nThe following are the illustrations of the state of the first test case at various points in time:","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ r, c \\in \\mathbb{Z}^+ $ denote the number of rows and columns of a grid.  \nLet $ G = (g_{i,j})_{1 \\le i \\le r,\\, 1 \\le j \\le c} $ be a grid where each cell $ g_{i,j} \\in \\{ \\texttt{\\#}, \\texttt{.}, \\texttt{W} \\} $.  \nLet $ W_0 = \\{ (i,j) \\mid g_{i,j} = \\texttt{W} \\} $ be the set of initially water cells.  \nDefine $ w(i,j) \\in \\mathbb{N}_0 \\cup \\{\\infty\\} $ as the earliest time (in seconds) at which cell $ (i,j) $ becomes water; $ w(i,j) = 0 $ if $ (i,j) \\in W_0 $, and $ \\infty $ if it never becomes water.\n\n**Constraints**  \n1. $ 1 \\le t \\le 10^4 $  \n2. $ 1 \\le r, c \\le 150000 $, $ r \\cdot c \\le 1500000 $  \n3. Total sum of $ r \\cdot c $ across all test cases $ \\le 1500000 $  \n4. At least one $ \\texttt{W} $ exists  \n5. All $ \\texttt{W} $'s are in row 1  \n6. No $ \\texttt{\\#} $ appears in row 1  \n\n**Water Propagation Rules**  \nWater spreads from a cell $ (i,j) $ to adjacent cells in the next second **if and only if**:  \n- The target cell is $ \\texttt{.} $  \n- The target cell is directly below $ (i,j) $: $ (i+1,j) $, **or**  \n- The target cell is diagonally below-left: $ (i+1,j-1) $, **or**  \n- The target cell is diagonally below-right: $ (i+1,j+1) $  \n- The cell directly below the target (i.e., $ (i+2,j) $, $ (i+2,j-1) $, $ (i+2,j+1) $ respectively) is **not** a solid cell $ \\texttt{\\#} $.  \n\n**Objective**  \nFor each test case:  \n1. Compute $ w(i,j) $ for all $ (i,j) $ such that $ w(i,j) < \\infty $.  \n2. Output the maximum value of $ w(i,j) $ over all such cells.  \n3. Output a grid of $ r $ rows and $ c $ columns, where the $ j $-th character of the $ i $-th row is:  \n   - $ \\texttt{W} $ if $ w(i,j) = 0 $,  \n   - $ \\texttt{.} $ if $ w(i,j) = \\infty $,  \n   - $ \\texttt{d} $ if $ w(i,j) = d \\in \\mathbb{Z}^+ $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10253O","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}