버전 관리 IDE

많은 프로그래머는 프로젝트 파일을 관리하기 위해 버전 관리 시스템을 사용한다. 하지만 이런 시스템에는 사용자가 직접 저장해야만 버전이 기록된다는 단점이 있다.

여기서는 문자열을 삽입하거나 삭제할 때마다 자동으로 새 버전을 저장하는 IDE를 구현한다.

버퍼의 각 위치에는 왼쪽부터 오른쪽으로 1번부터 번호가 매겨진다. 처음에 버퍼는 비어 있고 버전 번호는 0이다.

$L[v]$ 는 버전 $v$ 에서의 버퍼 길이를 뜻하고, $v_{now}$ 는 명령을 실행하기 직전의 버전 번호이다. IDE에는 다음 세 가지 명령이 있다.

• 1 p s: 위치 $p$ 의 바로 뒤에 문자열 $s$ 를 삽입한다 ($0 \le p \le L[v_{now}]$). $p = 0$ 이면 버퍼의 맨 앞에 삽입한다. $s$ 의 길이는 1 이상 100 이하이다.
• 2 p c: 위치 $p$ 부터 $c$ 개의 문자를 삭제한다 ($p \ge 1$, $p + c \le L[v_{now}] + 1$).
• 3 v p c: 버전 $v$ 에서 위치 $p$ 부터 $c$ 개의 문자를 출력한다 ($p \ge 1$, $p + c \le L[v] + 1$).

첫 번째 명령은 항상 1번 명령이다. 1번 또는 2번 명령을 수행하면 버전이 1 증가하지만, 3번 명령은 버전을 바꾸지 않는다.

첫째 줄에 명령의 수 $T$ ($1 \le T \le 50,000$) 가 주어진다. 이어지는 $T$ 개의 줄에 명령이 하나씩 주어진다. 삽입되는 문자열의 총 길이는 $1,000,000$ 을 넘지 않는다.

입력을 미리 처리하는 것을 막기 위해, 각 명령은 다음과 같이 인코딩되어 주어진다. $d$ 는 지금까지 출력된 소문자 c 의 개수이다(처음에는 $d = 0$).

• 1번 명령은 1 p+d s 로,
• 2번 명령은 2 p+d c+d 로,
• 3번 명령은 3 v+d p+d c+d 로 주어진다.

따라서 각 명령을 읽은 뒤 앞의 숫자에서 $d$ 를 빼면 실제 인자 $p$, $c$, $v$ 를 얻는다.

3번 명령을 수행할 때마다 그 결과 문자열을 한 줄에 출력한다. 출력되는 문자열의 총 길이는 $200,000$ 을 넘지 않는다.