题目描述

假设 HansBug 的思维是一长串字符串（字符串中包含且仅包含 $26$ 个字母），现在的你，有一张神奇的药方，上面依次包含了三种操作：

• 获取第 $x$ 到第 $y$ 个字符中字母 $k$ 出现了多少次
• 将第 $x$ 到第 $y$ 个字符全部赋值为字母 $k$
• 将第 $x$ 到第 $y$ 个字符按照 $\text{a} \sim \text{z}$ 的顺序排序

所以这个关键的任务就交给你啦！

本题给定的字符串或讯问中出现的字母可能含有大写或小写，但本题对大小写不敏感。即相同的字母如果大小写不同请视为同一个。

输入格式

第一行包含两个整数 $n,m$，分别表示 HansBug 的思维所包含的字母个数和药方上操作个数。

第二行包含一个长度为 $n$ 的字符串，表示 HansBug 的思维。

接下来 $m$ 行，每行表示一个操作，格式如下：

• 1 x y k 表示将第 $x$ 到第 $y$ 个字符中 $k$ 出现的次数输出
• 2 x y k 表示将第 $x$ 到第 $y$ 个字符全部替换为 $k$
• 3 x y 表示将第 $x$ 到第 $y$ 个字符按照 $\text{a} \sim \text{z}$ 的顺序排序

输出格式

输出为若干行，每行包含一个整数，依次为所有操作 $1$ 所得的结果。

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

8 10
cbBCaBbA
1 1 7 A
3 1 3
2 2 7 b
2 1 7 c
1 2 2 c
3 2 5
3 2 7
2 1 3 A
3 1 4
2 1 5 b

1
1

提示

对于 $100\%$ 的数据满足：$1\leq n,m\leq 50000$。