003 - お詫びの準備

時間制限 1 秒 / メモリ制限 64 MB / 得点 100 / x 0 /


TLE
1sec
MLE
64MB
得点
100

あらすじ

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

用語辞典

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

お店のルール

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

問題の要約

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

入力

t k c
chear1
chear2
  .
.
.
chearc
s1 name1 num1
s2 name2 num2
.
.
.
st namet numt

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

出力

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

制約

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

  • 10 ≦ t ≦ 106
  • 10 ≦ k,c,cheari ≦ 1000
  • 1 ≦ numi ≦ 10
  • nameiは20文字以内である。また、登場するグループは1以上107以下である。

入出力例

まえがき

ここでの解説では、ミスについて以下の言葉を定義する。
一人も来ていないはずのグループを呼んでしまったミス -> [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

解説

今回来たグループは5名で来たTaroさんと1人で来たSatoさんのみである。
Taroさんのグループは4人しかそろっていないため、"Not enough human"である。
その後、左の列に5人目のTaroさんのグループが来たため、Taroさんのグループ人数は揃った。この場合下図の用に並んでおり、TaroさんのグループはSatoさんがじゃまをして固まって並ぶことが出来ていない状況である。
この状況でTaroさんのグループを呼んだとしても、Taroさんは固まって並ぶことが出来ていないため"Not enough human"である。
その後、Satoさんのグループが呼ばれた。Satoさんは1人なのでそもそも他の人たちは関係なく、席も1人用の席が1つ残っているためSatoさんは無事店内にはいることが出来、"Good job"である。このとき、Satoさんは並んでいる場所から抜ける。
この状態でTaroさんのグループが呼ばれた場合、全員揃っていてなおかつ固まって並んでいて、席は足りているので店内にはいることが出来、"Good job"である。
1人で待っている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

解説

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

入力例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