1335D.md (1923B)
1 Source: https://codeforces.com/problemset/problem/1335/D 2 3 D. Anti-Sudoku 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given a correct solution to a Sudoku puzzle. If you don't know what Sudoku is, you can read about it [here](https://en.wikipedia.org/wiki/Sudoku). 22 23 The picture below shows a correct Sudoku solution: 24 25  Blocks are bordered in bold black. 26 27 Your task is to change at most $9$ elements of this field (i. e., choose some $1 \le i, j \le 9$ and change the number at the position $(i, j)$ to any other number in the range $[1; 9]$) to make it anti-sudoku. The anti-sudoku is the $9 \times 9$ field, in which: 28 29 * Any number in this field is in the range $[1; 9]$; 30 * Each row contains at least two equal elements; 31 * Each column contains at least two equal elements; 32 * Each $3 \times 3$ block (you can read what a block is following the link above) contains at least two equal elements. 33 34 It is guaranteed that a solution exists. 35 36 You have to answer $t$ independent test cases. 37 38 Input 39 40 The first line of the input contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then $t$ test cases follow. 41 42 Each test case consists of $9$ lines; each line consists of $9$ characters from $1$ to $9$ without any whitespaces — the correct solution of the Sudoku puzzle. 43 44 Output 45 46 For each test case, print the answer — the initial field with at most $9$ changed elements so that the obtained field is anti-sudoku. If there are several solutions, you can print any. It is guaranteed that the answer exists. 47 48 Example 49 50 Input 51 52 ``` 53 1 54 55 154873296 56 57 386592714 58 59 729641835 60 61 863725149 62 63 975314628 64 65 412968357 66 67 631457982 68 69 598236471 70 71 247189563 72 ``` 73 74 Output 75 76 ``` 77 154873396 78 336592714 79 729645835 80 863725145 81 979314628 82 412958357 83 631457992 84 998236471 85 247789563 86 ```