结果比较方式为全文比较（过滤行末空格及文末换行）。

题目描述

市档案馆保存着一份卷宗编号串 $s$，由小写字母组成，长度为 $n$，字符按位置从 $1$ 到 $n$ 编号。编号串并非一成不变：校勘科会不时修订其中的字符，而编目科则需要反复核查其中的片段。

编目科关心的是片段的规整程度。对于一段编号串，若存在某个字符串 $t$，使得该段恰好由 $t$ 首尾相接重复 $k$ 次拼接而成（$k$ 为正整数；$k=1$ 时 $t$ 就是这段编号串本身），则称这段编号串可以重复 $k$ 次。一段编号串可能以多种方式拼出，编目科只认其中最大的 $k$，称为这段编号串的最大重复次数。

校勘科与编目科的业务交替到达，共 $q$ 次，每次是以下两种之一：

• 修订：把编号串中第 $x$ 个字符改为小写字母 $c$；
• 核查：询问当前编号串中从第 $l$ 个到第 $r$ 个字符（含两端）组成的片段的最大重复次数。

请对每次核查，输出对应片段的最大重复次数。

输入格式

从文件 period.in 中读入数据。

• 第一行两个正整数 $n, q$，分别表示编号串长度与业务次数；
• 第二行一个长度为 $n$ 的小写字母字符串，表示初始编号串 $s$；
• 接下来 $q$ 行，每行描述一次业务，格式为 1 x c（修订）或 2 l r（核查），含义同上。

输出格式

输出到文件 period.out 中。

每次核查输出一行一个正整数，表示该片段的最大重复次数。

样例

6 4
ababab
2 1 6
2 1 4
2 1 3
2 5 5

3
2
1
1

样例 1 解释

第一次核查的片段是 ababab：试 $t$ 为单个字符，拼 $6$ 次应得到六个相同字符，不符；试 $t$ 为 ab，拼 $3$ 次恰好得到 ababab，符合；$k$ 更大时 $t$ 的长度不足 $2$，已不可能。故答案为 $3$。

第二次核查的片段是 abab，由 ab 拼 $2$ 次得到，答案为 $2$。

第三次核查的片段是 aba：试 $t$ 为单个字符拼 $3$ 次，得到的是三个相同字符，不符；此外没有更长的 $t$ 能把长度 $3$ 的片段拼出 $2$ 次以上，只有 $t$ 取片段本身可行，答案为 $1$。

6 3
ababac
2 1 6
1 6 b
2 1 6

1
3

12 3
cdcdcdcdcdcd
2 1 12
2 1 6
2 1 4

6
3
2

样例 3 解释

第一次核查的片段是 cdcdcdcdcdcd，长度为 $12$：试 $t$ 为单个字符，拼 $12$ 次应得到十二个相同字符，不符；试 $t$ 为 cd，拼 $6$ 次恰好得到该片段，符合。故答案为 $6$。

第二次核查的片段是 cdcdcd，由 cd 拼 $3$ 次得到，答案为 $3$。第三次核查的片段是 cdcd，由 cd 拼 $2$ 次得到，答案为 $2$。

数据范围

对于所有测试数据，保证：

• $1 \le n, q \le 10^5$；
• $s$ 由小写字母组成，长度为 $n$；
• 对于每次修订，$1 \le x \le n$，$c$ 为小写字母；
• 对于每次核查，$1 \le l \le r \le n$。

各测试点的约束如下：

• 特殊性质 A：没有修订操作，即所有业务均为核查。