问题陈述
给你一个字符串 S 长度 N,由小写英文字母组成。
处理给定的 Q 查询。有两种查询方式,如下所示:
1 p c:设置 p- 第一个字符 S 到角色 c.2 l r:打印最常见的字母出现的次数 l-th 通过 r第一个字符 S.
约束
- 1\le N\le 2\times 10^5
- 1\le Q\le 2\times 10^5
- S 是一个长度为的字符串 N,由小写英文字母组成。
- 1\le p\le N
- c 是一个小写英文字母。
- 1\le l\le r\le N
输入
输入由标准输入按以下格式给出:
N Q
S
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
每个查询 \text{query}_Q 采用以下格式之一给出:
1 p c
2 l r
输出
打印对问题陈述中提出的查询的响应,以换行符分隔。
示例输入 1
6 4 abbabc 2 1 3 2 1 6 1 5 d 2 1 6
示例输出 1
2 3 2
- 的 1-st 通过 3-rd 字符 S 是
abb。其中,b出现最频繁,即 2 次。因此,打印 2 为 1-st 查询。 - 的 1-st 通过 6第一个字符 S 是
abbabc。其中,b出现最频繁,即 3 次。因此,打印 3 为 2-nd 查询。 - 对于 3-rd查询,设置 5- 第一个字符 S to
d, 制作 S=abbadc. - 的 1-st 通过 6第一个字符 S 是
abbadc。其中,a和b出现最频繁,即 每个 2 次。因此,打印 2 为 4-第一个查询。
示例输入 2
8 4 nooutput 1 5 a 1 4 y 1 6 f 1 1 q
示例输出 2
示例输入 3
7 6 atcoder 2 1 7 1 1 r 2 1 7 1 2 r 2 1 7 1 4 r
示例输出 3
1 2 3