AT_arc225_a [ARC225A] Four Coloring

There is an $ N \times N $ grid $ X $ . Let $ (i,j) $ denote the cell at the $ i $ -th row from the top and the $ j $ -th column from the left. We call two cells that share an edge **adjacent**. Cell $ (i,j) $ is painted with color $ X_{i,j} $ . The color is one of $ 1,2,3,4 $ , and **adjacent cells are painted with different colors**. You will prepare an $ N \times N $ grid $ Y $ and paint each cell. Let $ Y_{i,j} $ denote the color painted on cell $ (i,j) $ of $ Y $ . Find one way of painting that satisfies the following conditions. - The color of each cell of $ Y $ is one of $ 1,2,3,4 $ . **Adjacent cells may have the same color.** - For any two adjacent cells $ (i_1,j_1) $ and $ (i_2,j_2) $ , the following holds. - If $ |X_{i_1,j_1} - X_{i_2,j_2}|=1 $ , then $ |Y_{i_1,j_1} - Y_{i_2,j_2}|\ge 2 $ . - If $ |X_{i_1,j_1} - X_{i_2,j_2}|\ge2 $ , then $ |Y_{i_1,j_1} - Y_{i_2,j_2}|\le 1 $ . It can be proved that a way of painting satisfying the conditions always exists.

The input is given from Standard Input in the following format: > $ N $ $ X_{1,1} $ $ X_{1,2} $ $ \ldots $ $ X_{1,N} $ $ X_{2,1} $ $ X_{2,2} $ $ \ldots $ $ X_{2,N} $ $ \vdots $ $ X_{N,1} $ $ X_{N,2} $ $ \ldots $ $ X_{N,N} $

Output a $ Y $ satisfying the conditions in the following format: > $ Y_{1,1} $ $ Y_{1,2} $ $ \ldots $ $ Y_{1,N} $ $ Y_{2,1} $ $ Y_{2,2} $ $ \ldots $ $ Y_{2,N} $ $ \vdots $ $ Y_{N,1} $ $ Y_{N,2} $ $ \ldots $ $ Y_{N,N} $

### Sample Explanation 1 For the input $ X $ and the output $ Y $ , for example, looking at the two adjacent cells $ (1,1) $ and $ (1,2) $ , we have the following. - $ |X_{1,1} - X_{1,2}| = |1 - 2| = 1 $ - $ |Y_{1,1} - Y_{1,2}| = |4 - 1| = 3 $ Also, looking at the two adjacent cells $ (2,2) $ and $ (3,2) $ , we have the following. - $ |X_{2,2} - X_{3,2}| = |1 - 3| = 2 $ - $ |Y_{2,2} - Y_{3,2}| = |3 - 4| = 1 $ In this way, it can be confirmed that $ Y $ satisfies the conditions for any two adjacent cells, so this is a correct answer. ### Sample Explanation 2 Adjacent cells of $ Y $ may have the same color. ### Constraints - $ 2 \le N \le 500 $ - $ 1 \le X_{i,j} \le 4 $ - **Adjacent cells** of $ X $ **are painted with different colors.** - All input values are integers.