Background

Rookie HansBug scratched his head countless times in the Chinese exam, but his mind was still completely blank.

Problem 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