問題文

あなたは、モンスターの調教師です。モンスター「高橋君」を育てて、所持金を出来るだけ増やしましょう！

高橋君はたくさんのスキルを持ち、それらをトレーニングで向上させながら、野良モンスターを討伐して報酬を稼ぐことが出来ます。

高橋君が持つスキルは N = 10 種類で、はじめ全てのスキルのレベルは 0 です。各スキルのレベルは最大 10 まで上げることが出来ます。また、現在のあなたの所持金は 1000 円です。

T = 1000 ターンが与えられます。各ターンには、以下の 3 種類の行動からどれか 1 つを行うことが出来ます。

• アルバイト： 所持金が 1000 円増える。
• トレーニング： N = 10 種類のスキルから 1 つを選び、そのスキルのトレーニングを 1 回行う。
  • スキルのレベルを k-1 から k (1≦k≦10) に上げるには、k 回のトレーニングが必要である。各回のトレーニングには 10000×2^k 円の費用がかかる。
  • レベル 10 のスキルについてトレーニングを行おうとした場合は失敗し、所持金は減らない。
  • 所持金が足りない場合もトレーニングに失敗し、所持金は減らない。
• 討伐： M = 30000 個の野良モンスターの討伐依頼から、どれか 1 つを選んで受注する。
  • i 番目の依頼には、10 種類のスキルの要求レベル S_{i,1}, S_{i,2}, ..., S_{i,10} と基本報酬額 C_i が設定されている。
  • 要求レベルに達していないスキルがあっても依頼を受注することは出来るが、1 種類のスキルについてレベルが 1 不足するごとに報酬が半減する。（詳しくは下記の計算式を参照）
  • すべてのスキルが要求レベル以上である場合、討伐は大成功し、報酬は 10 倍となる。
  • また、各依頼には討伐申込開始ターン A_i と討伐申込締切ターン B_i も設定されている。
    • A_i ターン目より早く、または B_i ターン目より遅くその依頼を受注することは出来ない。このような依頼を受注しようとした場合、何も起こらずにターンが終了する。（A_i ターン目または B_i ターン目ちょうどの受注は可能）
  • 報酬は締切に近ければ近いほど高くなり、締切ターンでの報酬は開始ターンの 10 倍となる。
  • より具体的には、実報酬額は以下の計算式で計算される。
    • (実報酬額) = floor((基本報酬額 C_i) × (締切報酬レート) × (スキル倍率))
    • 締切報酬レートは、受注ターンを X として以下となる。
      • (締切報酬レート) = 1 + 9 × (X - A_i) ÷ (B_i - A_i)
    • スキル倍率は、すべてのスキルが要求レベル以上であるとき 10、そうでないとき (1/2)^Y となる。
      • ここで、Y は要求レベルに達していないスキルすべてについての不足するレベルの総和である。
    • より厳密には、当ページ下部の「疑似コード」セクションを参照せよ。
  • 各依頼は一度しか受注することが出来ない。一度受注した依頼を再度受注しようとした場合、何も起こらずにターンが終了する。

1000 ターンの間の行動を出力し、最終的な所持金を最大化してください。

制約

• T = 1000
• N = 10
• M = 30000
• 各 i (1≦i≦M) について、1 ≦ A_i < B_i ≦ T, 1 ≦ C_i ≦ 10^{15}
• 各ペア i, j (1≦i≦M, 1≦j≦N) について、0 ≦ S_{i,j} ≦ 10
• 与えられるすべての値は整数

入力

入力は以下の形式で与えられる。

T N M
A_1 B_1 C_1 S_{1,1} S_{1,2} ... S_{1,N}
A_2 B_2 C_2 S_{2,1} S_{2,2} ... S_{2,N}
:
A_M B_M C_M S_{M,1} S_{M,2} ... S_{M,N}

出力

1000 ターンの間の行動を出力せよ。

出力は以下の形式で行うこと。

Command_1
Command_2
:
Command_{1000}

• Command_i は i ターン目に行う行動を表し、以下のように指定する。
  • トレーニングを行う場合、1 A_i とする。A_i (1≦A_i≦N) は、i ターン目にトレーニングを行うスキルの番号である。
  • 討伐依頼の受注を行う場合、2 B_i とする。B_i (1≦B_i≦M) は、i ターン目に受注する討伐依頼の番号である。
  • アルバイトを行う場合、3 とする。

入力生成

この項は必ずしも目を通す必要はない。

各テストケースにおける M 個の討伐依頼は、それぞれ独立に以下のアルゴリズムで生成されたものである。

1. 討伐申込可能期間を、「短期間」「中期間」「長期間」の 3 つから、均等な確率でランダムに選択する。
2. 討伐申込可能期間 L_i を決定する。短期間の場合は 2 ～ 10、中期間の場合は 11 ～ 100、長期間の場合は 101 ～ 1000 の間で、均等な確率でランダムで決定される。
3. 討伐申込開始ターン A_i を決定する。1 ～ T - L_i + 1 の間で、均等な確率でランダムに決定される。 B_i = A_i + L_i - 1 となる。
4. スキルの要求レベルを、高い順に決定していく。
   • 1 番目に高い要求レベルは、1～10 の間でランダムに決定される。これを s_1 とする。
   • 2 番目に高い要求レベルは、0～s_1 の間でランダムに決定される。これを s_2 とする。
   • 3 番目に高い要求レベルは、0～s_2 の間でランダムに決定される。これを s_3 とする。
   • これを繰り返し、 s_{10} まで決定する。
5. s をランダムに並び替えたものを、その討伐依頼の要求レベル S_i とする。
6. 要求レベルの和を Sum とすると、基準報酬額 M_i は M_i = 1.3^{Sum} で決定される。これに 1～2000 のランダムに決定された整数値を掛け、小数点以下を切り捨てた値を基本報酬額 C_i とする。

採点

各テストケースにおける点数は、1000 ターン後のあなたの所持金額そのものである。

テストケースは 30 個与えられる。全てのテストケースの点数の相乗平均が、その提出の得点となる。1 ケースでも出力が不正であった場合、提出の得点は 0 点となる。

ただし、サンプル入力についてのみ、最終的な所持金額を 0.01 倍した値を上記の得点にさらに加算する。この結果が提出の最終得点である。

追記 点数が大きすぎて順位表が見づらいため、点数をさらに 0.0001 倍したものを最終点数とする。

疑似コード

報酬の計算について、以下の疑似コードを利用して良い。これは、t ターン目に i 番目の討伐依頼を受注した際の実報酬額である。

    double AddMoney = C[i];
    AddMoney *= (1 + 9 * (double)(t - A[i]) / (B[i] - A[i]));
    int SkillLack = 0;
    for (int j = 0; j < N; j++) SkillLack += max(0, S[i][j] - SkillLevel[j]);

    if (SkillLack == 0) AddMoney *= 10;
    else {
        AddMoney *= pow(0.5, SkillLack);
        AddMoney += 1e-9;
    }
    Money += (long long)AddMoney;

入力例1

入力ファイルはこちらから(zip)

採点結果の「example_01」が、こちらのデータとなります。このデータも採点対象（相乗平均の計算に使われる 30 ケースのうちの 1 つ）となります。