Candy Compress

You are developing a mobile game called Candy Compress. In this game, there are several colored candies lined up from left to right. There are $26$ possible colors. At any point in time, the player can choose to add a candy at any position or to remove a subset of neighboring candies to get points depending on the colors of the removed candies.

To develop the game, you need to implement the following data structure. Initially, the data structure loads a $1$-indexed string of $n$ characters, which represents the colors of the initial candies. The string consists only of uppercase Latin characters (A to Z). After loading the string, there are $q$ operations to support:

• Operation 1: Insert the uppercase Latin character $c$ into the string so that it is at the $i$-th position in the new string. In particular, $i = 1$ means inserting $c$ at the beginning of the string. It is guaranteed that $1 ≤ i ≤ m + 1$, where $m$ is the length of the string just before this operation.
• Operation 2: Remove the characters from the $l$-th to the $r$-th position, inclusive. It is guaranteed that $1 ≤ l ≤ r ≤ m$, where $m$ is the length of the string just before this operation.

For each Operation 2, the data structure must determine the characters that are removed, so the game can calculate the points to award. In other words, you must find the content of the string from the $l$-th to the $r$-th position just before the operation.

The first line of input contains two integers $n$ and $q$ ($1 ≤ n ≤ 300\,000$; $1 ≤ q ≤ 300\,000$). The second line contains a string of $n$ uppercase Latin characters, the initial string to be loaded. Each of the next $q$ lines is one of the following operations:

1. 1 $c$ $i$ is Operation 1. It is guaranteed that $c$ is an uppercase Latin character and $1 ≤ i ≤ m + 1$, where $m$ is the length of the string just before this operation.
2. 2 $l$ $r$ is Operation 2. It is guaranteed that $1 ≤ l ≤ r ≤ m$, where $m$ is the length of the string just before this operation.

The operations are given in the order they are performed. There is at least one Operation 2.

For each Operation 2, in order, output one line containing the characters removed by that operation.