In 1776, a Committee of Five was chosen to draft the Declaration of Independence of the USA, among them John Adams, Thomas Jefferson and Benjamin Franklin. From June 11 to July 5 they worked tirelessly to write such important document.

It wasn't written correctly in the first attempt, and many many changes had to be made. Since in that time there weren't such great and time-saving utilities like git and version control, they had a very simple but time consuming way to keep old versions of the document.

Suppose Thomas Jefferson wanted to add a line to a version i of the document. Instead of changing the actual document in version i, he would use a letter copying press, a machine just invented by James Watt just around that time, to copy the version i to a new sheet of paper, and then would modify this new sheet of paper. This paper would then be stored so it could be copied later. As each modification creates a new version of the document, the kth modification will create the version k of the document. You can assume the version 0 of the document is an empty piece of paper.

As everything was written in ink and the committee doesn't like to contradict itself, each modification could only add some lines to the end of the document, or erase some lines from the beginning of the document.

Your task is to simulate the making of the Declaration of Independence. Each sentence is represented as an integer number. You need to process the following queries:

• E v x — Copy the document with version v, then add sentence x to the end of the copied document
• D v — Copy the document with version v, then remove the first sentence of the copied document

Queries are numbered from one. The document with version 0 is empty.