AT_arc225_a [ARC225A] Four Coloring

$ N \times N $ のグリッド $ X $ があります。上から $ i $ 行目、左から $ j $ 列目のマスを $ (i,j) $ で表します。辺を共有する $ 2 $ マスを **隣接する** と呼ぶことにします。 マス $ (i,j) $ は色 $ X_{i,j} $ で塗られています。色は $ 1,2,3,4 $ のいずれかであり、**隣接するマスは異なる色で塗られています**。 あなたは $ N \times N $ のグリッド $ Y $ を用意し、各マスに色を塗ります。 $ Y $ のマス $ (i,j) $ に塗る色を $ Y_{i,j} $ と表します。 以下の条件を満たすような色の塗り方を $ 1 $ つ求めてください。 - $ Y $ の各マスの色は $ 1,2,3,4 $ のいずれかである。 **隣接するマスの色は同じでも良い。** - 隣接する任意の $ 2 $ マス $ (i_1,j_1), (i_2,j_2) $ について、以下が成り立つ。 - $ |X_{i_1,j_1} - X_{i_2,j_2}|=1 $ ならば $ |Y_{i_1,j_1} - Y_{i_2,j_2}|\ge 2 $ - $ |X_{i_1,j_1} - X_{i_2,j_2}|\ge2 $ ならば $ |Y_{i_1,j_1} - Y_{i_2,j_2}|\le 1 $ なお、条件を満たすような色の塗り方は必ず存在することが証明できます。

入力は以下の形式で標準入力から与えられる。 > $ 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} $

条件を満たす $ Y $ を以下の形式で出力せよ。 > $ 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 入力された $ X $ 、出力した $ Y $ それぞれについて、例えば隣接する $ 2 $ マス $ (1,1), (1,2) $ を見ると、以下のようになります。 - $ |X_{1,1} - X_{1,2}| = |1 - 2| = 1 $ - $ |Y_{1,1} - Y_{1,2}| = |4 - 1| = 3 $ また、隣接する $ 2 $ マス $ (2,2), (3,2) $ を見ると、以下のようになります。 - $ |X_{2,2} - X_{3,2}| = |1 - 3| = 2 $ - $ |Y_{2,2} - Y_{3,2}| = |3 - 4| = 1 $ このように、 $ Y $ は隣接する任意の $ 2 $ マスに対して条件を満たすことが確かめられるため、正解となります。 ### Sample Explanation 2 $ Y $ の隣接するマスの色は同じでも構いません。 ### Constraints - $ 2 \le N \le 500 $ - $ 1 \le X_{i,j} \le 4 $ - $ X $ の**隣接するマスは異なる色で塗られている。** - 入力される値は全て整数