5632번 - 버젼 관리 IDE

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

오늘은 새로운 문자열을 추가하거나 삭제할 때 마다 자동으로 새로운 버젼을 저장하는 IDE를 구현해보려고 한다.

버퍼의 위치는 왼쪽부터 오른쪽까지 1번부터 번호가 매겨져 있다. 가장 처음에 버퍼는 비어있고, 버젼 번호는 0이다.

IDE에는 3가지 명령이 있으며, L[v]는 버젼 v에서 버퍼의 길이를 나타낸다. vnow는 명령을 실행시키기 전의 버젼 번호이다.

• 1 p s: 위치 p의 이후에 문자열 s를 삽입한다. (0 ≤ p ≤ L[vnow]) p가 0인 경우에는 버퍼의 가장 앞에 문자열을 추가하는 것이다. s는 1~100글자로 이루어진 문자열이다.
• 2 p c: 위치 p부터 c개의 문자를 제거한다. (p ≥ 1, p+c ≤ L[vnow]+1)
• 3 v p c: 버젼 v에서 위치 p부터 c개의 문자를 출력한다. (p ≥ 1, p+c ≤ L[v]+1)

첫 명령은 항상 1번 명령이며, 1번과 2번 명령을 수행한 뒤에 버젼은 1 증가한다.

첫째 줄에 명령의 수 T (1 ≤ T ≤ 50,000)가 주어진다. 다음 T개의 줄에는 명령이 주어진다. 삽입된 문자열의 총 길이는 1,000,000을 넘지 않는다.

입력을 선처리하는 것을 막기 위해서 다음과 같이 입력이 주어진다.

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

여기서 d는 출력한 알파벳 소문자 'c'의 개수이다.

예제 입력을 해독하면 다음과 같다.

6
1 0 abcdefgh
2 4 3
3 1 2 5
3 2 2 3
1 2 xy
3 3 2 4

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