AT_ahc044_a [AHC044A] Cleaning Up

ある会社では、現在働きやすい環境づくりを目指している。そこで新入社員が入社する 4 月から、社内の掃除を毎週行うことにした。 しかしながら、掃除当番は簡単に決められるものではない。 たとえば 1 人に負担をかけすぎてはならないことや、まだ仕事に慣れていない新入社員の負担は特に少なくしなければならないことなど、様々な制約がある。 また、掃除当番の決め方は「X さんの次は Y さんか Z さん」のように覚えやすいものでなければならない。 できるだけ制約通りになるように、掃除当番の決め方を最適化せよ。

ある会社には $ N $ 人の社員がおり、それぞれ $ 0 $ から $ N-1 $ までの番号が付けられている。 あなたは、各社員 $ i $ $ (0 \leq i \leq N-1) $ について整数 $ a_i $ と $ b_i $ を決め ( $ a_i=b_i $ でも構わない)、以下の規則で各週の掃除当番を割り当てることにした。 - 最初の週は、社員 $ 0 $ が掃除当番となる。 - それ以降の週については、前週の掃除当番を社員 $ x $ とし、前週が終わった時点で社員 $ x $ が掃除当番に $ t $ 回割り当てられたとして、今週の掃除当番は次のように決まる。 - $ t $ が奇数の場合: 社員 $ a_x $ - $ t $ が偶数の場合: 社員 $ b_x $ 各 $ i $ $ (0 \leq i \leq N-1) $ について、今後 $ L = 500\,000 $ 週間に社員 $ i $ に掃除当番を割り当てる回数の目標値 $ T_i $ が与えられる。 実際に社員 $ i $ に割り当てられる掃除当番の回数を $ t_i $ とするとき、誤差 $ \left|t_0 - T_0\right| + \left|t_1 - T_1\right| + \cdots + \left|t_{N-1} - T_{N-1}\right| $ をできるだけ小さくせよ。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ L $ $ T_0 $ $ T_1 $ $ \cdots $ $ T_{N-1} $ - 全てのテストケースで、社員の数 $ N $ は $ 100 $ で固定である。 - 全てのテストケースで、週数 $ L $ は $ 500\,000 $ で固定である。 - $ 0 \leq T_i \leq 10\,000 $ を満たす。 - $ T_0 + T_1 + \cdots + T_{N-1} = L $ を満たす。 - 入力はすべて整数である。

以下の形式で標準出力に出力せよ。 > $ a_0 $ $ b_0 $ $ a_1 $ $ b_1 $ $ \vdots $ $ a_{N-1} $ $ b_{N-1} $ ここで $ 0 \leq a_i \leq N-1 $ および $ 0 \leq b_i \leq N-1 $ を満たさない $ i $ $ (0 \leq i \leq N-1) $ が存在する場合、WA と判定される。 [例を見る](https://img.atcoder.jp/ahc044/PnJFT8lu.html?lang=ja&seed=0&output=sample)

### 得点 出力した掃除当番の決め方における誤差を $ E $ とするとき、 $ 10^6-E $ 点が得られる。 ここで、得点が負の値にならないことが保証される。 合計で 150 個のテストケースがあり、各テストケースの得点の合計が提出の得点となる。 一つ以上のケースで不正な出力や制限時間超過をした場合、提出全体の判定が WA や TLE となる。 コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数の参加者が得た場合、提出時刻に関わらず同じ順位となる。 ### 入力生成方法 $ L $ 以上 $ U $ 以下の整数値を一様ランダムに生成する関数を $ \mathrm{rand}(L, U) $ と表すとき、入力生成方法は次のようになる。 1. 各 $ 0 \leq i \leq N-2 $ について、 $ T_i $ の値を $ T_i = \mathrm{rand}(0, 10000) $ により生成する。 2. 総和 $ S=T_0+\cdots+T_{N-2} $ が $ 0\leq L-S\leq 10000 $ を満たすならば $ T_{N-1}=L-S $ として入力を確定させる。そうでなければ、1. に戻って生成をやり直す。 ### ツール(入力ジェネレータ・ビジュアライザ) - [Web版](https://img.atcoder.jp/ahc044/PnJFT8lu.html?lang=ja): ローカル版より高性能でアニメーション表示が可能です。 - [ローカル版](https://img.atcoder.jp/ahc044/PnJFT8lu.zip): 使用するには[Rust言語](https://www.rust-lang.org/ja)のコンパイル環境をご用意下さい。 - [Windows用のコンパイル済みバイナリ](https://img.atcoder.jp/ahc044/PnJFT8lu_windows.zip): Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。 コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。