武大郎先生在长沙坡子街口开了个烧饼店,生意非常红火。佳佳是个好吃的孩子,每天都去买着吃,久而久之,他发现武大郎烙饼的动作很有规律:武大郎不停地往锅里加饼,或者将锅内所有的饼一起翻转,或者当锅内的饼超过K张时,将锅内最下面的烧饼拿出来堆放到已经烙好的饼堆上面。
这样做了多次后,佳佳看得眼花缭乱,做烧饼的顺序与最后叠放的烧饼顺序发生了很大变化,为了弄清楚这些变化,因此佳佳在心中默默地给每个饼都起了一个名字(不过由于烧饼太多,有可能两个不同的饼起了同样的名字),现在问题是,给出初始的烧饼序列以及武大郎的若干操作过程,求出最后的烧饼顺序。
数据范围:
10%的数据满足0<=N<=10,0<=M,K<=10
50%的数据满足0<=N<=100000,0<=M<=100000,0<=K<=100000
100%的数据满足0<=N<=1000000,0<=M<=1000000,0<=K<=1000000
文件的第1行是3个整数N,M,K(0<= N<= 1000000,0<= M <= 1000000,0<=K<=1000000)。N表示佳佳来之前已有的饼数,M表示佳佳来之后观察武大郎的动作数,K表示锅子里的最多烧饼数。
接下来N行,第i+1行给出了第i个烧饼的名字(从上到下依次给出,最先给出的是最后一张饼,如图1(1))
接下来M行表示武大郎的动作,每次动作可能为:
ADD(NAME),表示武大郎往锅里添加了一个名字为NAME的新烧饼(饼名字均为长度不超过3的由英文字母组成的字符串);
ROTATE,表示武大郎做了一次翻饼的动作。若锅内饼数不足K,则将所有的饼翻转。
在输出文件中从上往下依次给出所有每个烧饼的名字,每个名字占一行。