되돌리기

시간 제한2초메모리 제한128 MB

요약
이전 t초 동안의 명령들을 역순으로 취소하는 undo 명령이 다른 undo까지 되돌릴 수 있는 텍스트 편집기를 시뮬레이션해 최종 텍스트를 구합니다.
난이도

보통10점 중 6점

유형
스택, 시뮬레이션, 이분 탐색, 배열
정답자
아직 제출이 없습니다

문제

민식이는 다음 두 명령만 지원하는 텍스트 편집기를 만들었다.

  • type c: 현재 글의 맨 뒤에 문자 c를 추가한다.
  • undo t: 이 명령이 실행되기 직전부터 과거 t초 동안 실행된 명령들을 역순으로 되돌린다.

처음 편집기의 내용은 비어 있다.

다음 과정을 생각해 보자.

  • 1초: type a
  • 2초: type b
  • 3초: type c
  • 5초: undo 3

3초가 끝났을 때 글은 abc이다. 5초에 실행된 undo 3은 직전 3초 동안 실행된 명령을 역순으로 되돌리므로, c가 지워지고 이어서 b도 지워진다. 따라서 a만 남는다.

되돌리기 명령도 나중의 되돌리기 명령에 의해 되돌려질 수 있다.

다음 과정을 보자.

  • 1초: type a
  • 2초: type b
  • 3초: undo 2
  • 4초: undo 2

2초에는 글이 ab이다. 3초에는 직전 2초 동안의 명령이 모두 되돌려져 빈 글이 된다. 4초에는 3초에 실행된 되돌리기가 먼저 되돌려지고, 그다음 2초에 실행된 type b가 되돌려진다. 따라서 마지막에는 a가 남는다.

명령과 각 명령이 실행된 시간이 주어질 때, 모든 명령을 수행한 뒤 남는 글을 구하시오.

입력

첫째 줄에 명령의 개수 N이 주어진다.

둘째 줄부터 N개의 줄에 명령과 그 명령이 실행된 시간이 주어진다. 시간은 항상 오름차순으로 주어진다. type c에서 c는 알파벳 소문자이다. undo t에서 t는 1 이상 10^9 이하의 자연수이다. N은 50 이하의 자연수이다.

출력

모든 명령을 수행한 뒤 편집기에 남아 있는 글을 출력한다.

예제5

  1. 예제 1

    입력
    4
type a 1
type b 2
type c 3
undo 3 5
    예상 출력
    a

  2. 예제 2

    입력
    4
type a 1
type b 2
undo 2 3
undo 2 4
    예상 출력
    a

  3. 예제 3

    입력
    3
type a 1
undo 1 2
undo 1 3
    예상 출력
    a

  4. 예제 4

    입력
    4
type a 1
type b 2
type c 3
undo 10 1000
    예상 출력
    abc

  5. 예제 5

    입력
    1
undo 1 1
    예상 출력