AT_ahc073_a [AHC073A] Circles of Inversion

魔法使いの高橋くんは、「反転の魔法陣」を使って、いくつもの目的地を決められた順に巡ろうとしている。 あらかじめ描いておいた魔法陣を一つ選び、現在位置に新たに描いた魔法陣と反応させると、選んだ魔法陣を中心として現在位置と点対称な位置へ一瞬で転移できる。 転移に使った魔法陣は消えるが、転移前の位置に描いた魔法陣は残り、次の転移に使うことができる。 高橋くんは、出発前にいくつかの魔法陣を好きな場所に描いておくことができる。 魔法陣の配置と歩行・転移の使い方を工夫し、できるだけ少ない操作ですべての目的地を順に巡る方法を考えてほしい。 

$ N\times N $ マスの盤面がある。 左上のマスの座標を $ (0,0) $ とし、そこから下方向に $ i $ マス、右方向に $ j $ マス進んだ先のマスの座標を $ (i,j) $ とする。 魔法使いの高橋くんが盤面上を移動する。 高橋くんの初期位置 $ s=(s_i,s_j) $ と、順番に訪れる $ M $ 個の目的地 $ g_0,\ldots,g_{M-1} $ が与えられる。 あなたは、あらかじめ盤面上の好きなマスに $ K $ 個の魔法陣を描く。 高橋くんと魔法陣、または複数の魔法陣が同じマスにあってもよく、互いに移動を妨げない。 以下の操作を繰り返す。 - 歩行：高橋くんを上下左右の隣接マスへ移す。 移動先は盤面内でなければならない。 - 転移：魔法陣が存在するマスを一つ選び、高橋くんの現在位置に新たな魔法陣を描く。 高橋くんは、選んだマスを中心として現在位置と点対称な位置へ転移する。 すなわち、操作前の高橋くんの位置を $ (i,j) $ 、選んだマスの座標を $ (a,b) $ として、高橋くんを $ (2a-i,2b-j) $ へ移す。 選んだマスの魔法陣を一つ消し、出発地点 $ (i,j) $ に描いた新たな魔法陣を残す。 転移先が盤面内にある場合だけ実行できる。 他の魔法陣は変化しない。 初期位置からすべての目的地を指定順に歩行のみで訪れるために必要な最小の操作回数を $ T $ とする。 すなわち、 $ T $ は初期位置から最初の目的地まで、および隣り合う目的地間のマンハッタン距離の総和である。 操作は合計で最大 $ T $ 回まで行うことができる。 各操作の直後、高橋くんが次の目的地にいれば、その目的地を訪れたものとする。 次に訪れるべき目的地以外に到着しても、訪れた目的地の数は増えない。 後で訪れる予定の目的地に先に到着した場合も、その目的地の順番が来たら改めて訪れる必要がある。 魔法陣の初期配置と操作列を決め、できるだけ短い操作列ですべての目的地を指定順に訪れよ。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $ $ T $ $ s_i $ $ s_j $ $ g_{0,i} $ $ g_{0,j} $ $ \vdots $ $ g_{M-1,i} $ $ g_{M-1,j} $ ここで $ g_r=(g_{r,i},g_{r,j}) $ は $ r $ 番目の目的地である。 各値は以下の制約を満たす。 - $ N=128 $ - $ M=150 $ - $ K=3 $ - $ T $ は前述の歩行のみで全目的地を訪れるための最小操作回数である。 - すべての座標の成分は $ 0 $ 以上 $ N $ 未満の整数である。 - $ s,g_0,\ldots,g_{M-1} $ はすべて異なる。

以下の形式で標準出力に出力せよ。 > $ a_0 $ $ b_0 $ $ \vdots $ $ a_{K-1} $ $ b_{K-1} $ $ \mathrm{op}_0 $ $ \vdots $ $ \mathrm{op}_{A-1} $ 最初の $ K $ 行には、あらかじめ描く $ K $ 個の魔法陣の座標 $ (a_k,b_k) $ を任意の順序で出力せよ。 各座標の成分は $ 0 $ 以上 $ N $ 未満の整数でなければならない。 続いて操作を $ 1 $ 行に一つずつ、以下の形式で出力せよ。 - 上下左右への歩行：それぞれ `U`、`D`、`L`、`R` - マス $ (a,b) $ の魔法陣を使う転移：`J` $ a $ $ b $ 転移で指定する座標は $ 0\leq a,b

### 得点 出力した操作列の長さを $ A $ 、指定順に訪れた目的地の数を $ V $ とする。 このとき、以下の得点が得られる。 \\\[ \\begin{cases} M+T-A+1 & (V=M) \\\\ V+1 & (V<M) \\end{cases} \\\] 合計で 150 個のテストケースがあり、各テストケースの得点の合計が提出の得点となる。 一つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定が WA や TLE となり、提出の得点は 0 点となる。 コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数の参加者が得た場合、提出時刻に関わらず同じ順位となる。 ### 入力生成方法 $ N^2 $ 個のマスから相異なる $ M+1 $ 個を順序付きで一様に選び、先頭を $ s $ 、残りを順に $ g_0,\ldots,g_{M-1} $ とする。 $ T $ は選ばれた初期位置と目的地から計算する。 ### ツール(入力ジェネレータ・ビジュアライザ) - [Web版](https://img.atcoder.jp/ahc073/A21qfZSs.html?lang=ja): ローカル版より高性能でアニメーション表示が可能です。 - [ローカル版](https://img.atcoder.jp/ahc073/A21qfZSs.zip): 使用するには[Rust言語](https://www.rust-lang.org/ja)のコンパイル環境をご用意下さい。 コンパイルが通らない場合は `rustup update` をお試し下さい。 - [Windows用のコンパイル済みバイナリ](https://img.atcoder.jp/ahc073/A21qfZSs_windows.zip): Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。 コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。 ご注意下さい。