Algorithmen Übungen WS13/14

Die Firma ACME ist ständig auf der Suche nach neuen Mitarbeitern. Dafür wurde ein ganz ausgefuchster Einstellungstest entwickelt, bei dem die Bewerber maximal P Punkte erreichen können. Die erzielten Punkte p_i jedes Bewerbers i werden von ACME erfasst. Interessanterweise ist der Test so beschaffen, dass die erzielten Punkte der verschiedenen Bewerber gleichverteilt im Intervall {0,1,...,P} sind. Die Bewerber werden anhand ihrer erreichten Punkte in k verschiedene Eignungslevel (0,1,...,k-1) eingruppiert, so dass Eignungslevel 0 die Bewerber enthält die 0 bis P/k-1 Punkte erzielt haben, Eignungslevel 1 die Bewerber mit P/k bis 2*P/k-1 Punkte und so weiter.

ACME führt die Einstellungstests an mehren Tagen durch. Am Ende eines Tages werden die erreichten Punkte pro Bewerber erfasst. Da jeden Tag andere Fragen in den Tests verwendet werden müssen, aber die Tests ungefähr gleich schwer bleiben sollen, führt die Sekretärin von ACME stichprobenartige Tests zur Überprüfung des Schwierigkeitsgrades durch. Dazu werden nach dem Eintragen der Bewerberergebnisse des Tages die Bewerber eines gewählten Eignungslevels nach Punkten absteigend sortiert ausgegeben. Nach dem letzten Einstellungstest sollen alle Teilnehmer absteigend sortiert nach ihrer Punktzahl ausgegeben werden. Insgesamt ist bei der Sortierung der Teilnehmer zu beachten, dass bei Punktgleichstand zweier Bewerber, der zuerst ausgegeben wird, der auch den Test zuerst gemacht hat. Für die Bewerber wird in den geforderten Ausgaben immer die ID i ausgegeben. Die ID wird fortlaufend vom ersten bis zum letzten Tag vergeben, z.B. am Tag 1 haben die Bewerber 0,1,2,...,8 teilgenommen und an Tag 2 dann die Bewerber 9,10,11,...,20.

Input

Die Eingabe beginnt mit einer Zeile, die den genauen Testablauf beschreibt. Diese enthält die Maximalpunktzahl P (0 < P <= 10⁸), die Anzahl der Eignungslevel k (2 < k <= 10⁵) und die Anzahl der Tage d (0 < d <= 10⁶), an denen Einstellungstests stattfinden. Für jeden Tag mit Einstellungstest sind zwei Zeilen gegeben. Die erste Zeile enthält die erreichten Punkte der Bewerber dieses Tages. Die zweite Zeile enthält das Eignungslevel, dessen Bewerber absteigend sortiert nach erreichten Punkten ausgegeben werden sollen. Es kann angenommen werden, dass weniger als 20 Bewerber pro Tag teilnehmen.

Output

Nach jedem Tag sollen jeweils die IDs der Bewerber (aller vorangegangenen Tage) des gegebenen Eignungslevels absteigend sortiert nach Punkten in einer Zeile ausgegeben werden. Wenn es (noch) keine Bewerber in dem Eignungslevel gibt, soll none ausgegeben werden. Nach dem letzten Tag sollen zusätzlich die IDs aller Bewerber (aller Eignungslevel) absteigend sortiert nach Punkten in einer Zeile ausgegeben werden.

Example

Input 1:
100 5 5
9 6 78 63
3
36 69 55
2
60 27
1
25 31 84 22
3
17 91 32
0

Output 1:
2 3
6
4 8
2 5 3 7
13 0 1
14 11 2 5 3 7 6 4 15 10 8 9 12 13 0 1

Input 2:
100 5 5
7
4
65 69
1
21 92
2
36 85 33
1
18 99
3

Output 2:
none
none
none
5 7 3 
2 1 
9 4 6 2 1 5 7 3 8 0