크래이피쉬 글쓰는 기계(Crayfish scrivener)

활자 인쇄기를 발명한 독일 대장장이인 요하네스 구텐베르크는 레오나르도가 열렬히 존경하는 사람이었다.

레오나르도는 크래이피쉬 글쓰는 기계 — il gambero scrivano —로 불리는 매우 단순한 타자 기계를 설계하여 구텐베르크에게 존경을 표시하였다.

이것은 단순한 현대의 타자기와 매우 비슷하며, 단지 두 개의 명령어만 받아들인다.

하나는 그 다음 문자를 타자하는 것이고, 다른 하나는 가장 최근의 명령어들을 취소(undo)하는 것이다.

이 타자 기계의 주목할 만한 특징은 취소 기능이며, 이는 매우 강력한 기능이다:

취소 명령은 자기 자신, 즉 취소 명령어에 대해서도 적용될 수 있다.

해야 할 일

여러분이 할 일은 크래이피쉬 글쓰기 기계와 같이 동작하는 소프트웨어를 구현하는 것이다:

빈 텍스트에서 시작하고, 사용자가 입력한 명령어의 순서들을 받아들이고,

다음과 같이 텍스트의 현재 상황의 특정 위치에 대한 질의를 수행한다.

TypeLetter(L) : a, …, z으로부터 선택된 하나의 소문자 L을 텍스트의 끝에 추가한다.

UndoCommands(U) : 양의 정수 U에 대해, 가장 최근의 U 개의 명령어를 취소한다.

GetLetter(P) : 음이 아닌 인덱스 P에 대해, 현재 텍스트에서 위치 P의 문자를 되돌려준다.

텍스트에서 첫 번째 문자의 인덱스는 0 이다. (이 질의는 명령어가 아니어서 취소 명령어에서는 무시된다.)

UndoCommands(U)에서는 이전의 U개의 명령어를 역순으로 취소한다.

만약 취소될 명령어가 TypeLetter(L)라면, 이것은 현재 텍스트의 끝에서부터 L을 삭제한다.

만약 취소될 명령어가 어떤 값 X에 대해 UndoCommands(X) 라면 이것은 이전의 X개의 명령어를 원래의 순서대로 다시 실행한다.

예제

하나의 가능한 호출순서에 대해서 각 호출후의 텍스트의 상태를 보인다.

입력

첫줄에 n(1 ≤ n ≤ 1,000,000)이 입력되는데 이것은 입력 줄 수이다. 그 다음부터 n줄에 걸쳐 질의가 입력되고 공백 후 값이 입력된다.

T : TypeLetter U : UndoCommands P : GetLetter

출력

P : GetLetter의 해당 문자를 한 줄에 하나씩 출력한다.

예제1

출처

IOI 2012 day1 3

크래이피쉬 글쓰는 기계(Crayfish scrivener) 2초 512MB