AT_ahc070_a [AHC070A] Ward the Village

あなたは日本の山奥にある村の村長で、毎年お盆になると発生する怪異に頭を悩ませていた。 今年は巫女の占いにより、村中で $ 10000 $ 回の怪異が起こることが分かった。 そこで、怪異の起こる場所のできるだけ近くに魔除けのお札を立て、被害を抑えることにした。 占いは怪異の起こる場所と順番を告げるが、猶予はない。 あなたは村外れの社を出て村を巡り、怪異の発生と並行してお札を立てていかねばならない。 お札は、社または直前に立てたお札から神力を受け継いで初めて魔除けの力を持つ。 神力の通り道は巫女の祈祷で $ 3 $ 通りまで開くことができ、どの位置関係に開くかは、社を出る前にあなたが決める。 村が受ける被害をできるだけ小さく抑えてほしい。

村は $ N\times N $ マスに区切られている。 左上のマスの座標を $ (0,0) $ とし、そこから下方向に $ i $ マス、右方向に $ j $ マス進んだ先のマスの座標を $ (i,j) $ とする。 各ターン $ t=0,1,\cdots,N^2-1 $ に怪異が発生するマスの座標 $ (a_t,b_t) $ が、あらかじめ入力として与えられる。 まず、神力の通り道となる $ M $ 個の位置関係 $ (i_0,j_0),\cdots,(i_{M-1},j_{M-1}) $ を自由に定める。 ただし、 $ 0 $ 以上 $ M $ 未満のすべての $ m $ について、 $ i_m $ と $ j_m $ は $ 0 $ 以上 $ N $ 未満の整数でなければならない。 初期状態では、危険度は $ 0 $ 、あなたの位置 $ P $ は社のあるマス $ (0,0) $ であり、お札は $ 1 $ 枚も立っていない。 この状態から、以下の操作を $ t=0,1,\cdots,N^2-1 $ の順に行う。 1. $ 0 $ 以上 $ M $ 未満の整数 $ m_t $ を選ぶ。 2. あなたは $ P $ から下方向に $ i_{m_t} $ マス、右方向に $ j_{m_t} $ マス移動する。盤面の上下と左右はループしており、移動前の $ P $ が $ (i,j) $ のとき、移動後の $ P $ は $ ((i+i_{m_t})\bmod N,\ (j+j_{m_t})\bmod N) $ となる。 3. 移動後の $ P $ のマスにお札を立てる。既にお札が立っているマスに重ねて立てても構わない。一度立てたお札は最後のターンまで残り続ける。 4. マス $ (a_t,b_t) $ に怪異が発生し、危険度に $ \mathrm{floor}(d_t\times\sqrt{t+1}) $ が加算される。ここで $ d_t $ は、マス $ (a_t,b_t) $ とお札が立っているマスとのマンハッタン距離の最小値である。 マス $ (i,j) $ とマス $ (i',j') $ のマンハッタン距離は $ |i-i'|+|j-j'| $ である。 あなたの移動とは異なり、この距離の計算では盤面の上下と左右はループしないことに注意せよ。 操作 4 の時点では必ず $ 1 $ 枚以上のお札が立っているため、 $ d_t $ は常に定まる。 また、 $ (a_t,b_t) $ にお札が立っている場合は $ d_t=0 $ となり、危険度は増えない。 全 $ N^2 $ ターンが終了した時点での危険度をできるだけ小さくせよ。 #### 例 説明のため、 $ N=5, M=3 $ とし、最初の $ 3 $ ターンだけを考える。 位置関係を $ (i_0,j_0)=(0,1) $ 、 $ (i_1,j_1)=(1,0) $ 、 $ (i_2,j_2)=(3,4) $ と定め、 $ m_0=0, m_1=1, m_2=2 $ を選ぶ。 下図では、星が立てたお札、赤い印が怪異の発生するマス、青い丸と矢印があなたの位置と移動を表す。 t = 0 m₀ = 0, +(0, 1) mod 5 d₀ = 2, +2 01234 01234 P: (0, 0) → (0, 1) t = 1 m₁ = 1, +(1, 0) mod 5 d₁ = 3, +4 01234 01234 P: (0, 1) → (1, 1) t = 2 m₂ = 2, +(3, 4) mod 5 d₂ = 0, +0 01234 01234 P: (1, 1) → (4, 0) $ t=0 $ では、 $ (0,0) $ から $ (0,1) $ へ移動してお札を立てる。 怪異は $ (0,3) $ に発生するため $ d_0=2 $ であり、危険度に $ \mathrm{floor}(2\sqrt{1})=2 $ が加算される。 $ t=1 $ では $ (1,1) $ へ移動し、怪異は $ (0,4) $ に発生する。 怪異が発生したマスから、直前のターンに $ (0,1) $ へ立てたお札までの距離は $ 3 $ 、このターンに $ (1,1) $ へ立てたお札までの距離は $ 4 $ である。 したがって $ d_1=3 $ であり、危険度に $ \mathrm{floor}(3\sqrt{2})=4 $ が加算される。 $ t=2 $ では、盤面がループしているため、 $ (1,1) $ から下に $ 3 $ マス、右に $ 4 $ マス移動した先は $ (4,0) $ となる。 このマスにお札を立てた直後に同じマスで怪異が発生するため $ d_2=0 $ であり、危険度は増えない。 したがって、 $ 3 $ ターン終了時点での危険度は $ 2+4+0=6 $ となる。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ a_0 $ $ b_0 $ $ a_1 $ $ b_1 $ $ \vdots $ $ a_{N^2-1} $ $ b_{N^2-1} $ 各値は以下の制約を満たす。 - $ N=100 $ - $ M=3 $ - $ 0\leq a_t

以下の形式で標準出力に出力せよ。 > $ i_0 $ $ j_0 $ $ i_1 $ $ j_1 $ $ \vdots $ $ i_{M-1} $ $ j_{M-1} $ $ m_0 $ $ m_1 $ $ \vdots $ $ m_{N^2-1} $ [例を見る](https://img.atcoder.jp/ahc070/f4sYgUzY.html?lang=ja&seed=0&output=sample)

### 得点 全 $ N^2 $ ターンが終了した時点での危険度を $ D $ とする。 このとき、以下の得点が得られる。 \\\[ \\mathrm{round}\\left(\\frac{10^6\\times N^3}{D+1}\\right) \\\] 合計で 150 個のテストケースがあり、各テストケースの得点の合計が提出の得点となる。 一つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定が WA や TLE となり、提出の得点は 0 点となる。 コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数の参加者が得た場合、提出時刻に関わらず同じ順位となる。 ### 入力生成方法 $ N=100 $ と $ M=3 $ は固定である。 $ (a_0,b_0),\cdots,(a_{N^2-1},b_{N^2-1}) $ は、盤面の $ N^2 $ 個のマスの座標全体を一様ランダムに並べ替えたものである。 ### ツール(入力ジェネレータ・ビジュアライザ) - [Web版](https://img.atcoder.jp/ahc070/f4sYgUzY.html?lang=ja): ローカル版より高性能でアニメーション表示が可能です。 - [ローカル版](https://img.atcoder.jp/ahc070/f4sYgUzY.zip): 使用するには[Rust言語](https://www.rust-lang.org/ja)のコンパイル環境をご用意下さい。コンパイルが通らない場合は `rustup update` をお試し下さい。 - [Windows用のコンパイル済みバイナリ](https://img.atcoder.jp/ahc070/f4sYgUzY_windows.zip): Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。 コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。 **今回の短期コンテストから、生成AIの利用が一部の例外を除き、禁止となります。詳細は[こちらの記事](https://atcoder.jp/posts/short-ahc-llm-rules-ja)をご確認ください。**