K. 橘猫的后缀问题
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

今天橘猫打算教塑料后缀数组，只见他端上来一个长度为 $$$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。

Input

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

第一行输入一个正整数 $$$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$$$)，对应上述操作。

Output

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

Example
Input
5
abbaa
3
2 3
1 1 b
2 3
Output
4
3
Note

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

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

  • 5 a
  • 4 aa
  • 1 abbaa
  • 3 baa
  • 2 bbaa

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

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

  • 5 a
  • 4 aa
  • 3 baa
  • 2 bbaa
  • 1 bbbaa

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