AT_rcl_contest_2021_a 魔法使いXの戦い

Description

[problemUrl]: https://atcoder.jp/contests/rcl-contest-2021/tasks/rcl_contest_2021_a 魔法使いXはいまモンスターの大群と対峙しています。モンスターは $ N $ 匹いて、横一列に並んでいます。モンスターにはそれぞれ**強さ**があり、左から $ i $ 番目のモンスターの**強さ**を $ A_i $ と表します。魔法使いXが使える魔法は唯一つ、「パワーアップ」です。「パワーアップ」はモンスター1匹の**強さ**を、もう1匹のモンスターの**強さ**分だけ上げるという魔法です。具体的には以下のような手順を経ます。 1. **強さ**を変化させたいモンスターを1匹選ぶ。このモンスターの左からの位置を $ p $ とする。 2. モンスターをさらに1匹選ぶ。このモンスターの左からの位置を $ q $ とする。このとき $ p\ =\ q $ でもよい。 3. $ p $ 番目のモンスターの**強さ**が、\$A\_{p} = (A\_{p} + A\_{q}) \\% K\$ へと変化する。ここで、$ \%\ K $ は $ K $ で割った余りを表す。（$ K $ はこの世界における**強さ**の制限値で、**強さ**が $ K $ 以上になった場合はオーバーフローしてしまいます）また、魔法使いXは「パワーアップ」を最大 $ M $ 回まで唱えることができます。「パワーアップ」をかけるモンスターをうまく選び、魔法を唱え終わった後のそれぞれのモンスターの**強さ**をできるだけ小さい値にして、戦いを有利にしてください。各テストケースの得点およびこの問題の得点は、次のように計算されます。 - 1つのテストケースでは、以下の式でスコアが計算されます。 \\\[score = \\text{ceil}\\left(\\sum\_{i}(\\log\_{2}K - \\log\_{2}(A\_{i} + 1))\\right)\\\] なお、$ \text{ceil}(x) $ は $ x $ 以上の最小の整数を表します。また、魔法を唱え終わった後の $ A $ で $ 0 $ でない値が1個以下の場合、$ M\ -\ (魔法を唱えた回数) $ をスコアに加えます。 - テストケースは全部で $ 50 $ 個あります。各テストケースの得点の合計が、この問題の得点になります。

Input Format

入力は以下の形式で標準入力から与えられます。 1行目には整数 $ N $, $ M $, $ K $ がスペース区切りで与えられます。2行目には $ N $ 個の整数がスペース区切りで与えられます。 ```

\(\begin{array}{lll}
    N & M & K\\
    A_{ 0 } & \ldots & A_{ N-1 }
  \end{array}\)
```

- $ N $ はモンスターの数で、$ N\ =\ 300 $ を満たします。
- $ M $ はXが唱えられる魔法の回数で、$ M\ =\ 1000 $ を満たします。
- $ K $ は**強さ**の制限値で、$ K\ =\ 10^8 $ を満たします。
- $ A_{i} $ は左から $ i $ 番目のモンスターの**強さ**を表す整数で、$ 0\ を満たします。 $

Output Format

出力は $ M $ 行以下で、各行にはスペース区切りで $ 2 $ 個の整数を標準出力へ出力してください。 ```

\(\begin{array}{lll}
    p_{0} &  q_{0} \\
    \vdots &  \vdots \\
  \end{array}\)
```

- $ p_{i} $ は $ i $ 回目の「パワーアップ」の手順1で選んだモンスターの位置で、$ 0\

Explanation/Hint

### テストケースの生成について各ケースはテストケースジェネレータによって生成されています。テストケースジェネレータはページ下部のリンクより提供しています。各 $ A_{i} $ の値は、$ 1 $ 以上 $ K $ 未満の整数から一様ランダムに独立に選ばれます。 ### 配布物についてテストケースジェネレータ・テスター・サンプル入力データ・ビジュアライザを次のリンクから提供しています。 [テストケースジェネレータ・テスター・サンプル入力データ・ビジュアライザ (zip)](https://img.atcoder.jp/rcl-contest-2021/0c1b1f5593c50e8ecd8c76dda728d7ed.zip) ### ビジュアライザの説明入力ファイルと出力ファイルから、得点の計算および結果を可視化するビジュアライザを用意しました。 - このビジュアライザはデスクトップ版の [Google Chrome](https://www.google.co.jp/chrome/) および [Mozilla Firefox](https://www.mozilla.org/firefox/new/) の最新バージョン上で動作確認を行っています。全てのブラウザ環境で動作することを保証していません。 - このビジュアライザ上で計算された得点は、当コンテストでの得点ではありません。解答を AtCoder 上で提出する事によって採点が行われます。また、ビジュアライザ上で計算された得点は、当コンテスト上での得点を保証するものではありません。 - このビジュアライザを使用することによるあらゆる損害は保障しかねますので、予めご了承ください。ビジュアライザは配布物にも含まれ、使用方法については配布物内のREADME.htmlに書いてあります。 ### Sample Explanation 1 このケースは説明用のもので、入力の制約（ $ N\ =\ 300 $, $ M\ =\ 1000 $, $ K\ =\ 10^8 $）を満たしていません。