IOI(国際情報オリンピック) - joi2011-day4

出典: 第10回日本情報オリンピック 日本代表選手選考会

時間制限: 1秒

メモリ制限: 64MB

20XX 年，ついに JOI 国で行われることになった IOI には K 人の選手が参加した．選手には 1, 2, …, K と番号が付けられている．問題は全部で N 問出題され，各選手は各問題について 0 以上 100 以下の整数の点数を付けられる．

選手には N 問の合計点に応じてメダルが与えられる．メダルの与えられる詳しい条件は，たとえば金メダルについては次のように決まっている：

• G を，N 問の合計点が G 点以上の選手の人数が全体の \frac{1}{12} 以上となるような最大の値とする．このとき，金メダルが与えられる条件は，N 問の合計点が G 点以上であることである．

すでに競技が終了している問題が M 問あり，点数が確定している．IOI のウェブサイトで各選手の現在までの合計点を見ていたあなたは，金メダルを与えられることが確実な選手や金メダルを与えられる可能性のある選手がそれぞれどれだけいるのかが知りたくなった．

課題

各選手の現在までの合計点が与えられたとき，金メダルを与えられることが確実な選手，および，金メダルを与えられる可能性のある選手をそれぞれ番号順に出力するプログラムを作成せよ．

制限

1 \leq K \leq 100\,000	選手の人数
1 \leq N \leq 10\,000\,000	全体の問題数
0 \leq M \leq N	すでに終了した問題数
0 \leq P_i \leq 100 \times M	番号 i の選手の現在までの合計点

入力

標準入力から以下の入力を読み込め．

• 1 行目には整数 K, N, M が空白を区切りとして書かれており，選手の人数が K 人であること，全体の問題数が N 問であること，そのうちすでに終了した問題が M 問あることを表す．
• 続く K 行には各選手の得点が書かれている．i + 1 行目 (1 \leq i \leq K) には，番号 i の選手の現在までの合計点を表す整数 P_i が書かれている．

出力

標準出力に以下の内容を出力せよ．

• 初めの a 行は，金メダルを与えられることが確実な選手の番号を，1 行に 1 つずつ，小さい順に列挙していなければならない．ただし a は金メダルを与えられることが確実な選手の人数である．
• 続く 1 行には文字列 -------- (ハイフンが 8 個) を出力せよ．
• 続く b 行は，金メダルを与えられる可能性のある選手の番号を，1 行に 1 つずつ，小さい順に列挙していなければならない．ただし b は金メダルを与えられる可能性のある選手の人数である．

採点基準

• 採点用データのうち，配点の 20% 分については，K \leq 3\,000 を満たす．

入出力の例

入力例 1	出力例 1
15 3 2 0 30 50 100 0 190 10 50 100 80 90 200 50 100 0	12 -------- 4 6 9 11 12 14

入力例 2	出力例 2
5 4 2 0 50 100 150 200	-------- 1 2 3 4 5