Hamako Online Judge

TLE
1sec

MLE
64MB

得点
100

あらすじ

あなたはお店のウェートレスである。店の外で待っているお客を呼ばなければならない。
あなたは店の中で準備が出来ていないのにお客を呼んでしまったりまだ人数が揃っていないグループのお客を呼んでしまったり、といったミスによって店に入れないお客がいたかを報告書に書くのが日課だ。
しかし、今日の仕事の報告書を書くことになったあなたは最終的にどの客が並んでいたかを忘れてしまった。
幸い、客が左もしくは右に並んだという情報と、お客を呼んだタイミングは記録として残っている。もしかしたらミスをしていないかもしれないが、最終的に店に入れなかったお客にはお詫びしなければいけないので、リストアップすることにした。

用語辞典

ウェートレス　接客する人であり、あらすじにでてきたあなたのことを指す。
お客　お店に来て食事をしに来る人一人一人を指す
グループ　複数人のお客が同じ席で食事をする場合、その人達を１つのグループとしてまとめる。だがしかし、一人だけで食事をする場合でもその人１人だけでグループを組む。
お店　このお店は１つの机に１つのグループが座って食事をする店である。

お店のルール

あなたが働いているお店は、以下のルールを定めている。
その１　お客は一人ずつ列に並ぶ。

その２　お客は列の一番右か一番左にしか並べない。

その３　お客は並ぶ際にウェートレスに名前と何人で来たのかを告げる。
もし、グループで来ている場合、先に同じグループの人がどこかしらに並んでいる場合その中で最も早く並んでいる人の名前を伝え、同じグループの人が誰も並んでいない場合は自分の名前を告げる。

例1　今から出てくる３人のお客は同じグループである。
最初に来たTaroさん「Taroです。３人です。」
２番目に来たJiroさん「Taroです。３人です。」
３番目に来たSaburoさん「Taroです。３人です。」

その４　ウェートレスが店内にグループを呼ぶ場合、お客の名前と、そのグループが何人なのかを読み上げる。

例2「３名様でお待ちの予定の、Taroさまー」

例えそのグループが揃っていなくても、ウェートレスはくる予定の人数を読み上げる。
例1の場合でいうと、Taro,Jiro,Saburoが全員揃っていなくても「３名様でお待ちの予定の、Taroさまー」とウェートレスは読み上げるのだ。

その５　ウェートレスが店内にグループを呼んだ際、呼ばれたグループのお客は必ず人数が揃っていなければならない。また、１つのグループで固まっていて並んでいなければならない。

例3 列のどこかで例１に出てきたTaro,Jiro,Saburoがまばらに並んでいた場合Taroグループは入れない。
例4 列のどこかで例１に出てきたTaroとJiroとSaburoがくっついて並んでいた場合Taroグループは入れる。

その６　もし、同姓なおかつ同じ人数の別のグループが来た場合、その人達は入れない。
たとえば、３人待ちのTaroさんが待っている間に,このTaroさんグループとは無縁の3人待ちのTaroさんのグループのお客が並ぼうとした場合、ややこしくなるため後から来たTaroさんは並ぶことが出来ない。これは、最初に来た３人待ちのTaroさんグループが店を去った後でも適用される。

その７　例え揃っていたとしても席が用意できていなければそのグループお店にはいることは出来ない。
店には1人用からc人用までの席が数はバラバラだが用意されていて、その数はデータとしてちゃんと残っている。
たとえばc=3だった場合、
一人用が１０個
二人用が２２個
三人用が５個

のような感じだ。たまに、

一人用が０個
二人用が５個
三人用が１０個
のようにとある席が用意されていない場合もある。
一人用の席１つと二人用の席１つで三人用の席として使うみたいな、複数の席を合体することは禁止である。
三人用の席を二人のグループで使うといった、グループの人数が足りないのにそれより大きい人数用の席を使う行動も禁止である。
三人用の席を二人のグループと一人のグループで使うといった、複数のグループで１つの席を使うこと（いわゆる相席）も禁止である。
つまり、一つの席に一つのグループがぴったりの人数で使わなければならない。

そして、i人用の席が１つもない状態でi人のグループをもし呼んでしまった場合、そのグループは店の中にそのタイミングでは入れない。

その８　このお店は kより上のグループをお店の中には入れることが出来ない。そのため、今店の中にk個のグループがいる状態でまた新しいグループが入ってきた場合、今店の中にいる中で一番早く店に入ったグループが入れ替わりで抜ける。

その９　店内にいるグループは例え早く食べ終えても、自分のタイミングで店を抜け出すことは出来ない。

問題の要約

データが与えられるので、ルール通りに仕事をした場合最終的に並んでいた客を左から順に出力してください。

入力

t k c
chear₁
chear₂
  .
.
.
chear_c
s₁ name₁ num₁
s₂ name₂ num₂
.
.
.
s_t name_t num_t

tは与えられるデータの数 kは店に入るグループの上限 cは何人用の席まで数のデータがあるのかを示す。
chear_iはi人用の席が何個あるのかを示す値を示す。
ここまでに出てきた入力はすべて整数である。
s_i（アルファベット１文字） name_i(文字列) num_i(整数)はs_iのアルファベットによって違う意味を持つ。
s_iが'L'の場合、num_i人のグループのname_iが列の一番左に並んだことを示す。
s_iが'R'の場合、num_i人のグループのname_iが列の一番右に並んだことを示す。
s_iが'C'の場合、ウェートレスがnum_i人のグループのname_iを呼んだことを示す。

出力

最終的に並んでいたお客を左から順に出力する。もしも、同じグループのお客が連続して並んでいた場合、それらのグループはひとまとまりにして出力する。
１グループ出力するごとに改行すること。
また、１つのグループに対し出力するのは左からグループ名、そのグループが何人来る予定か、今そのグループが何人連続して並べているかとし、これらはカンマ区切りとする。
たとえば、Aというグループが全員で１０人くる予定で、今連続して二人並べているとしたらA,10,2となる。
どういうことかわからない人は入出力例の３をみること。

制約

全ての入出力ケースについて以下を満たす。

10 ≦ t ≦ 10⁶
10 ≦ k,c,chear_i ≦ 1000
1 ≦ num_i ≦ 10

⁷

入出力例

まえがき

ここでの解説では、ミスについて以下の言葉を定義する。
一人も来ていないはずのグループを呼んでしまったミス　-> [Ghost]
まだそのグループが全員揃っていないのにそのグループを呼んでしまったミス -> [Not enough human]
まだそのグループの人数と同じ数の席が用意できていない場合 -> [Not enough chear]
無事席に案内できた -> [Good job]

画像とかないですごめんね＞＜

入力例1

11 5 5
1
0
0
0
1
L Taro 5
L Taro 5
R Taro 5
R Taro 5
C Taro 5
L Sato 1
L Taro 5
C Taro 5
C Sato 1
C Taro 5
C Taro 1

出力例1

Perfect

解説

今回来たグループは５名で来たTaroさんと１人で来たSatoさんのみである。
Taroさんのグループは４人しかそろっていないため、"Not enough human"である。
その後、左の列に５人目のTaroさんのグループが来たため、Taroさんのグループ人数は揃った。この場合下図の用に並んでおり、TaroさんのグループはSatoさんがじゃまをして固まって並ぶことが出来ていない状況である。
この状況でTaroさんのグループを呼んだとしても、Taroさんは固まって並ぶことが出来ていないため"Not enough human"である。
その後、Satoさんのグループが呼ばれた。Satoさんは１人なのでそもそも他の人たちは関係なく、席も１人用の席が１つ残っているためSatoさんは無事店内にはいることが出来、"Good job"である。このとき、Satoさんは並んでいる場所から抜ける。
この状態でTaroさんのグループが呼ばれた場合、全員揃っていてなおかつ固まって並んでいて、席は足りているので店内にはいることが出来、"Good job"である。
１人で待っているTaroさんはそもそも来てすらいないので"Ghost"
ここでデータが終わって、この時点で並んでいる人は一人もいないのでPerfectを出力

入力例2

13 2 3
1
1
1
R Taro 1
R Jiro 2
R Jiro 2
R Saburo 1
R Siro 3
R Siro 3
R Siro 3
C Taro 1
C Saburo 1
C Jiro 2
C Saburo 1
C Siro 3
C Saburo 1

出力例2

Perfect

解説

１人用の席が最初から１つしかないことを頭の中に入れておいてほしい。
Taroさんを呼んだ時は１人用の席は１つあるので、無事店内に入れるので"Good job"
Saburoさんを呼んだ時は１人用の席はTaroさんがすでに使っており"Not enough chear"
Jiroさんのグループを呼んだ時は２人用の席は１つあるので、無事店内に入れるので"Good job"
２回目にSaburoさんを呼んだ時は店内にkと同等の数のグループがいて、Saburoさん自身もお店に入れる状況なのだが、SaburoさんとTaroさんが交代して座るわけではない。あくまでも無事に店内に入って、そのグループが座った瞬間に店を出て行くのだ。よって"Not enough chear"
Siroさんのグループを呼んだ時は３人目の席は１つあるので、無事店内に入れるので"Good job"
このとき、店内にいるグループがkを超える。今店内にいるグループで一番早く来たのはTaroさんなのでTaroさんはこの席を立ち、店の外へ出て行く。そのため、１人用の席が１つ用意が出来る。
３回目にSaburoさんを呼んだ時は１人用の席は１つ余っているので、無事店内に入れるので"Good job"。
ここでデータが終わって、この時点で並んでいる人は一人もいないのでPerfectを出力
もうこれ以降のデータはないので関係ないのだが、この時店を出るのはJiroさんのグループであり、２人用の席が１つ用意が出来る。

入力例3

11 1 1
0
L A 2
R B 1
L A 2
L C 2
L D 1
R E 2
R E 2
R F 3
R G 10
L C 1
R F 3

出力例3

C,1,1
D,1,1
C,2,1
A,2,2
B,1,1
E,2,2
F,3,1
G,10,1
F,3,1

解説

今回のデータでは一回もコールしていない。よって、並んだ全員が最終的に並んでいることとなる。
これと出力結果を照らし合わせてどのように出力するか確認してほしい。

入力例4

30 4 3
404
310
260
R LABAI 1
R ZNAWU 2
R ZNAWU 2
R FXESL 1
R PIZUV 2
R PIZUV 2
L LABAI 2
R FXESL 2
L LABAI 2
L ZNAWU 1
R FXESL 2
C ZNAWU 1
C LABAI 1
R ZFZQJ 2
R ZFZQJ 2
C ZNAWU 1
C LABAI 2
C ZFZQJ 2
C LABAI 2
C PIZUV 2
C ZFZQJ 2
C ZNAWU 1
C ZNAWU 2
C ZNAWU 2
C LABAI 2
C LABAI 1
C LABAI 2
C ZNAWU 2
C ZNAWU 2
C FXESL 2
C PIZUV 2

出力例4

FXESL,1,1

003 - お詫びの準備