Background

LHF’s biggest trait is being poor.
LHF’s biggest hobby is watching shopping TV shows.

Today, he was watching a shopping show again.
On the show, he saw a new type of text editor. It was very suitable for a poor person like him except for the price.

Because… it can calculate printing costs.
(The printing cost here depends on the number of different kinds of letters that have appeared.)

He was very interested and asks you to implement this feature.

Problem Description

This text editor supports the following operations:

• $\texttt{I x c}$: Insert a $c$ after the $x$-th letter.
• $\texttt{D x}$: Delete the $x$-th letter.
• $\texttt{R x y}$: Reverse the interval $[x,y]$ in the current text.
• $\texttt{P x}$: Output the position of the $x$-th letter in the initial text within the current text. In particular, if it does not exist, output $0$.
• $\texttt{T x}$: Output the $x$-th letter in the current text.
• $\texttt{Q x y}$: Output the number of different kinds of letters that have appeared in interval $[x,y]$ of the current text.

Input Format

The first line contains two integers $n,m$, representing the length of the initial text and the number of operations.
The second line contains a string of length $n$, representing the initial text.
The next $m$ lines each describe one operation.

Output Format

For every operation that requires output, print the result.

12 6
kimiwakawaii
R 2 4
P 4
D 1
I 0 w
T 3
Q 3 10

2
m
5

Hint

Constraints:

For $20\%$ of the testdata, $n \le 100$.
For $50\%$ of the testdata, $n \le 10000$.
For $100\%$ of the testdata, $1 \le n,m \le 10^5$, and the text contains only lowercase letters.

Sample Explanation:

1. The text does not change, but the positions of the $2$-nd and $4$-th letters in the initial text are swapped.
2. The current $2$-nd letter is the $4$-th letter of the initial text.
3. The text becomes $\texttt{imiwakawaii}$.
4. The text becomes $\texttt{wimiwakawaii}$.
5. This letter is $\texttt{m}$.
6. This segment is $\texttt{miwakawa}$, and the set of character kinds it contains is $\{\texttt{a},\texttt{i},\texttt{k},\texttt{m},\texttt{w}\}$, so the number of elements is $5$.

Translated by ChatGPT 5