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.
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 the sequence of books names in the pile after performing all operations. First line corresponds to the top book.