橘猫的后缀问题
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
Special Judge, 64bit IO Format: %lld

题目描述


今天橘猫打算教塑料后缀数组，只见他端上来一个长度为 n 的由小写字母组成的字符串，问塑料某个后缀在所有后缀中排第几大，然而塑料直接掏出了板子干掉了，还嘲讽了一番。


面对如此场景，橘猫灵机一动，给塑料布置了一道新题目：


给你一个长度为 n 的由小写字母组成的字符串 S，接下来会有 Q 次查询/修改操作：


  • 1 x c：修改操作，将位置 x 的字符改为 c；


  • 2 x：查询操作，询问 S 的从第 x 位开始的后缀\dagger的排名。


我们定义后缀的排名为在 S 所有后缀中按字典序排序后该后缀的下标（从 1 开始）。

字典序的定义为，对于两个字符串 s 和 t，找到左起第一个不同的字符 s_i 和 t_i。若找不到，则长度更短的字符串字典序更小；否则按字母表升序比较 s_i 和 t_i。

塑料看到这道新题心生怯意，于是他请你帮他做这道题，不过他发现了题目的最下方还有一行字：

保证初始字符串的每个字符和更新操作给出的每个字符都是从 {a,b,...,z} 中均匀随机抽取的。

\dagger 对于一个字符串 s，从第 x 位开始的后缀为 s_{x}s_{x+1}\dots s_{n} 如字符串 abcde 的从第 3 位开始的后缀为 cde。

输入描述:

本题每个数据点仅有一组测试样例。

第一行输入一个正整数 n (1 \leq n \leq 2 \times 10^5)，表示字符串 S 的长度；

第二行输入一个长度为 n 的字符串 S；

第三行输入一个正整数 Q (1 \leq Q \leq 2 \times 10^5) 表示询问次数；

接下来 Q 行，每行的输入格式为1 x c(1 \leq x \leq n, c \in \{a,b,...,z\}) 或2 x(1 \leq x \leq n)，对应上述操作。

输出描述:

对于每个询问操作，输出一个正整数 x 表示目标后缀的排名。
示例1

输入

复制 
5
abbaa
3
2 3
1 1 b
2 3

输出

复制 
4
3

备注:

样例仅为了方便理解题面作参考，不符合数据性质

在第一次询问时，后缀的排名如下：

  • 5 a

  • 4 aa

  • 1 abbaa

  • 3 baa

  • 2 bbaa

故长度为 3 的后缀排名为 4；

在第二次询问时，后缀的排名如下：

  • 5 a

  • 4 aa

  • 3 baa

  • 2 bbaa

  • 1 bbbaa

故长度为 3 的后缀排名为 3。