크레이피시 글쓰기 기계

활자 인쇄기를 발명한 독일의 대장장이 요하네스 구텐베르크는 레오나르도가 깊이 존경하는 인물이었다. 레오나르도는 구텐베르크에게 경의를 표하고자 "크레이피시 글쓰기 기계"(il gambero scrivano)라 불리는 매우 단순한 타자 기계를 설계하였다. 이 기계는 현대의 타자기와 비슷하지만 오직 두 종류의 명령만 받아들인다. 하나는 다음 문자를 입력하는 것이고, 다른 하나는 가장 최근의 명령들을 취소(undo)하는 것이다. 이 기계에서 가장 주목할 점은 취소 기능이 매우 강력하다는 것이다. 취소 명령은 자기 자신, 즉 다른 취소 명령에도 적용될 수 있다.

여러분이 할 일은 이 기계처럼 동작하는 프로그램을 구현하는 것이다. 빈 텍스트에서 시작하여 사용자가 입력하는 명령들을 순서대로 처리하고, 현재 텍스트의 특정 위치에 대한 질의에 답한다.

• Init() — 실행 시작 시 인자 없이 한 번만 호출되어 자료 구조를 초기화한다. 이 호출은 결코 취소되지 않는다.
• TypeLetter(L) — a부터 z까지의 소문자 하나인 L을 텍스트의 끝에 덧붙인다.
• UndoCommands(U) — 양의 정수 U에 대해, 가장 최근의 명령 U개를 취소한다.
• GetLetter(P) — 0 이상의 인덱스 P에 대해, 현재 텍스트에서 위치 P의 문자를 반환한다. 첫 문자의 인덱스는 0이다. (이 질의는 명령이 아니므로 취소 대상에 포함되지 않는다.)

Init() 이후 나머지 동작들은 임의의 순서로 0번 이상 호출될 수 있다. U는 그때까지 실행된 명령의 개수를 넘지 않으며, P는 항상 현재 텍스트의 길이보다 작다.

UndoCommands(U)는 직전의 U개 명령을 역순으로 취소한다. 취소하려는 명령이 TypeLetter(L)이면 현재 텍스트의 끝에서 그 문자 L을 지운다. 취소하려는 명령이 어떤 값 X에 대한 UndoCommands(X)이면, 그 직전의 X개 명령을 원래 순서대로 다시 실행한다.

다음은 한 가지 호출 순서와 각 호출 이후의 텍스트 상태를 보여 준다.

첫째 줄에 명령과 질의의 총 개수 L이 주어진다. 이어지는 L개의 줄에는 각각 하나의 명령 또는 질의가 주어진다.

• T L — TypeLetter(L)을 호출한다 (L은 소문자 한 글자).
• U U — UndoCommands(U)를 호출한다 (U는 양의 정수).
• P P — GetLetter(P)를 호출한다 (P는 0 이상의 정수).

각 줄의 첫 글자가 명령의 종류를 나타내며, 인자는 공백으로 구분된다.

GetLetter 질의가 반환한 문자를 호출된 순서대로 한 줄에 하나씩 출력한다.