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.
数据范围：$0 \le N \le 40000, \; 0 \le M \le 10^5, \; 0 \le K \le 40000$。