题目描述

给定一个长度为 $N$ 的字符串 $S$，由小写英文字母组成。

处理 $Q$ 个查询，有以下两种类型：

• 类型 $1$：将 $S$ 中第 $i_q$ 个字符更改为 $c_q$。（如果第 $i_q$ 个字符已经是 $c_q$，则不进行任何操作。）
• 类型 $2$：回答在 $S$ 的子串中从第 $l_q$ 个字符到第 $r_q$ 个字符（包括）之间出现的不同字符的数量。

约束条件

• $N$、$Q$、$i_q$、$l_q$ 和 $r_q$ 是整数。
• $S$ 是一个由小写英文字母组成的字符串。
• $c_q$ 是一个小写英文字母。
• $1 \leq N \leq 500000$
• $1 \leq Q \leq 20000$
• $|S| = N$
• $1 \leq i_q \leq N$
• $1 \leq l_q \leq r_q \leq N$
• 每个测试用例中至少有一个类型为 $2$ 的查询。

输入

输入以以下格式从标准输入中给出:

$N$ $S$ $Q$ $Query_1$ $\vdots$ $Query_Q$

这里，$Query_i$ 在第 $4$ 到第 $(Q+3)$ 行之间的内容是以下之一：

$1$ $i_q$ $c_q$ $2$ $l_q$ $r_q$

输出

对于每个类型为 $2$ 的查询，打印一个行，包含答案。

示例输入 1

7
abcdbbd
6
2 3 6
1 5 z
2 1 1
1 4 a
1 7 d
2 1 7

示例输出 1

3
1
5

在第一个查询中，cdbb 中包含三种字母：b、c 和 d，所以我们打印 $3$。

在第二个查询中，$S$ 被修改为 abcdzbd。

在第三个查询中，a 中包含一种字母：a，所以我们打印 $1$。

在第四个查询中，$S$ 被修改为 abcazbd。

在第五个查询中，$S$ 没有改变，仍然是 abcazbd。

在第六个查询中，abcazbd 中包含五种字母：a、b、c、d 和 z，所以我们打印 $5$。