Description

The exam has started, but HansBug's mind is still blank. Oh no! To be precise, it is a total mess. Your primary task now is to help HansBug organize his thoughts. Assume HansBug's thoughts form a long string (containing only the $26$ letters). Now you have a magic prescription that contains three operations in order:

1. Get how many times letter $k$ appears from the $x$-th to the $y$-th character.
2. Set all characters from the $x$-th to the $y$-th to letter $k$.
3. Sort the characters from the $x$-th to the $y$-th in $\text{a} \sim \text{z}$ order.

Just when you are overjoyed, his brain cells and RP have already been exhausted by previous nervousness, and there is still an $800$-word essay at the end of the paper. So this crucial task is up to you!

Input Format

The first line contains two integers $n, m$, denoting the number of letters in HansBug's thoughts and the number of operations on the prescription, respectively. The second line contains a string of length $n$, representing HansBug's thoughts.

Then follow $m$ lines, each describing an operation in the following format (positions are $1$-based and inclusive):

• 1 x y k means to output how many times $k$ appears from the $x$-th to the $y$-th character.
• 2 x y k means to replace all characters from the $x$-th to the $y$-th with $k$.
• 3 x y means to sort the characters from the $x$-th to the $y$-th in $\text{a} \sim \text{z}$ order.

Output Format

Output several lines, each containing an integer, which are the results of all type 1 operations in order.

10 5
ABCDABCDCD
1 1 3 A
3 1 5
1 1 3 A
2 1 2 B
1 2 3 B

1
2
2

Hint

Sample explanation:

Constraints:

This problem is case-insensitive.

Three additional hack testdata groups have been added, which are not in the table above, but it is guaranteed that $1 \le n, m \le 50000$.

Translated by ChatGPT 5