캔디 압축

당신은 Candy Compress라는 모바일 게임을 개발하고 있다. 이 게임에서는 색깔이 있는 캔디 여러 개가 왼쪽에서 오른쪽으로 한 줄로 놓여 있다. 색깔은 $26$가지가 있다. 플레이어는 언제든지 원하는 위치에 캔디를 추가하거나, 이웃한 캔디 일부를 제거할 수 있다. 제거한 캔디의 색깔에 따라 점수를 얻는다.

이 게임을 만들려면 다음 자료 구조를 구현해야 한다. 자료 구조는 처음에 $1$부터 시작하는 길이 $n$의 문자열을 읽는다. 이 문자열은 처음 놓인 캔디의 색깔을 나타낸다. 문자열은 대문자 알파벳 A부터 Z까지로만 이루어진다. 문자열을 읽은 뒤에는 지원해야 할 연산이 $q$개 있다.

• 연산 1: 대문자 알파벳 $c$를 문자열에 삽입하여, 새 문자열의 $i$번째 위치에 오도록 한다. 특히 $i = 1$이면 문자열의 맨 앞에 $c$를 삽입한다. 이 연산 직전 문자열의 길이를 $m$이라 하면 $1 ≤ i ≤ m + 1$이 보장된다.
• 연산 2: $l$번째부터 $r$번째 위치까지의 문자를 양 끝을 포함하여 제거한다. 이 연산 직전 문자열의 길이를 $m$이라 하면 $1 ≤ l ≤ r ≤ m$이 보장된다.

연산 2마다 게임이 줄 점수를 계산할 수 있도록, 제거되는 문자를 구해야 한다. 즉, 연산 직전 문자열에서 $l$번째부터 $r$번째 위치까지의 내용을 구해야 한다.

첫 줄에 두 정수 $n$과 $q$가 주어진다 ($1 ≤ n ≤ 300\,000$; $1 ≤ q ≤ 300\,000$). 둘째 줄에는 처음 읽어 들일 길이 $n$의 대문자 알파벳 문자열이 주어진다. 이어지는 $q$개의 줄에는 다음 형식 중 하나의 연산이 주어진다.

1. 1 $c$ $i$는 연산 1이다. $c$는 대문자 알파벳이며, $1 ≤ i ≤ m + 1$이다. 여기서 $m$은 이 연산 직전 문자열의 길이이다.
2. 2 $l$ $r$은 연산 2이다. $1 ≤ l ≤ r ≤ m$이다. 여기서 $m$은 이 연산 직전 문자열의 길이이다.

연산은 주어진 순서대로 수행한다. 연산 2는 적어도 하나 있다.

각 연산 2마다, 입력 순서대로 그 연산으로 제거되는 문자들을 한 줄에 출력한다.