271. Book Pile

time limit per test: 0.25 sec.
memory limit per test: 65536 KB
input: standard
output: standard



There is a pile of N books on the table. Two types of operations are performed over this pile:
- a book is added to the top of the pile,
- top K books are rotated. If there are less than K books on the table, the whole pile is rotated.
First operation is denoted as ADD(S) where S is the name of the book, and the second operations is denoted as ROTATE.
The maximum number of books is no more than 40000. All book names are non-empty sequences of no more than 3 capital Latin letters. The names of the books can be non-unique.

Input
The first line of input file contains 3 integer numbers N, M, K (0 <= N <= 40000; 0 <= M <= 100000; 0 <= K <= 40000). The following N lines are the names of the books in the pile before performing any operations. The book names are given in order from top book to bottom. Each of the following M lines contains the operation description.

Output
Output the sequence of books names in the pile after performing all operations. First line corresponds to the top book.

Sample test(s)

Input
2 3 2
A
B
ADD(C)
ROTATE
ADD(D)

Output
D
A
C
B
[submit]
[forum]

Author:Michael R. Mirzayanov
Resource:ACM ICPC 2004-2005, NEERC, Southern Subregional Contest
Date:Saratov, October 7, 2004











Server time: 2017-11-23 19:47:43Online Contester Team © 2002 - 2016. All rights reserved.