题目描述

You are given a string $S$ of length $N$ consisting of lowercase English letters.

Process $Q$ queries of the following two types:

• Type $1$: change the $i_q$-th character of $S$ to $c_q$. (Do nothing if the $i_q$-th character is already $c_q$.)
• Type $2$: answer the number of different characters occurring in the substring of $S$ between the $l_q$-th and $r_q$-th characters (inclusive).

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

请处理以下两种类型的 $Q$ 查询：

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

输入格式

第一行为整数 $N$；
第二行为字符串 $S$；
第一行为整数 $Q$；
接下来有 $Q$ 行查询操作，每行包含以下内容之一：

$1$ $i_q$ $c_q$

$2$ $l_q$ $r_q$

输出格式

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

样例 #1

样例输入 #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

说明

数据规模与约定

• $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$ 类型的查询。

样例 $1$ 解释

在第一个查询中，cdbb 包含三种字母：b, c, 和 d`，因此我们打印 $3$ 。

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

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

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

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

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