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).

-----Constraints-----
 - N, Q, i_q, l_q, and r_q are integers.
 - S is a string consisting of lowercase English letters.
 - c_q is a lowercase English letter.
 - 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
 - There is at least one query of type 2 in each testcase.

-----Input-----
Input is given from Standard Input in the following format:
N
S
Q
Query_1
\vdots
Query_Q

Here, Query_i in the 4-th through (Q+3)-th lines is one of the following:
1 i_q c_q

2 l_q r_q

-----Output-----
For each query of type 2, print a line containing the answer.

-----Sample Input-----
7
abcdbbd
6
2 3 6
1 5 z
2 1 1
1 4 a
1 7 d
2 1 7

-----Sample Output-----
3
1
5

In the first query, cdbb contains three kinds of letters: b , c , and d, so we print 3.
In the second query, S is modified to abcdzbd.
In the third query, a contains one kind of letter: a, so we print 1.
In the fourth query, S is modified to abcazbd.
In the fifth query, S does not change and is still abcazbd.
In the sixth query, abcazbd contains five kinds of letters: a, b, c, d, and z, so we print 5.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = '"""\nAtCoder Beginner Contest 157  E - Simple String Queries\n\n文字列Sに対して、\nクエリ1：i番目の文字をcに変更\nクエリ2：S[l~r]に何種類の文字があるか\n\n各クエリについて、律儀に文字を変えて、l~rについて何種類あるか調べると間に合わないはず。\n\n~~~ABCCDC~~~\n        ↑を別の文字にした時に、最後に出てくるCがその二個左、のような情報をちゃんと残したい。\n→ 最後の位置が知りたいとかではなく、lとrを指定した時に、その間にあるかが知りたい（具体的な位置が知りたいわけではない）\n\u3000そうするt、a〜zについて、l~rに存在するか、みたいな確認ができそう\n\nN <= 5 * 10**5\nQ <= 2 * 10**4\nなので、bisect使えば間に合うのか？よくわからん\n\nSとしてではなく、現時点で何文字目がなになのかも持っておいたほうが楽か。\n\n"""\n\nimport bisect\n\nN = int(input())\nS = input()\nQ = int(input())\n\n# 現時点でどこに何があるか\ncS = [""] * N\n# ある文字の位置\nchar_idxs = [[]for _  in range(26)]\n\n# i番目は文字s、を保存\nfor i,s in enumerate(S):\n    cS[i] = s\n    char_idxs[ord(s) - 97].append(i)\n\nquery = [tuple(map(str, input().split())) for _ in range(Q)]\n\n\n\n\nfor q,a,b in query:\n    \n    # q == 1の時、a番目の文字をbに置き換え\n    if q == "1":\n        # 現時点の文字と置き換え後が同じなら何もしない\n        if cS[int(a) - 1] == b:\n            continue\n        else:\n            #print("---", char_idxs[ord(cS[]) - 97], int(a)-1, bisect.bisect_right(char_idxs[ord(b) - 97], int(a)-1))\n            # a番目の文字を書き換える\n\n            \n            idx = bisect.bisect_right(char_idxs[ord(cS[int(a)-1]) - 97], int(a)-1)\n            # idxの左の値がa番目であれば、それを消す\n            if char_idxs[ord(cS[int(a)-1]) - 97][idx-1] == int(a)-1:\n                # delの方が早いか？\n                char_idxs[ord(cS[int(a)-1]) - 97][idx-1:idx] = []\n            \n            # bの文字がa番目にあるよ、を保存\n            bisect.insort_right(char_idxs[ord(b) - 97], int(a) - 1)\n\n            # 置き換え\n            cS[int(a) - 1] = b\n\n    # q == 2の時、範囲の文字種の個数を調べる\n    else:\n        cnt = 0\n        for i in range(26):\n            # そもそもその文字が文字列全体になければ考えない\n            if len(char_idxs[i]) == 0: continue\n            # bisect_leftで a-1 を入れられる場所を探して、その時に右にある値がb-1以下であれば含まれる\n            l = bisect.bisect_left(char_idxs[i], int(a)-1)\n            #r = bisect.bisect_right(char_idxs[i], int(b)-1)\n\n            # char_idxs[i][l]はa-1より右に文字種iが初めて出てくる位置なので、それがb-1を含む右側にあればOK\n            if l < len(char_idxs[i]) and char_idxs[i][l] <= int(b)-1:\n                cnt += 1\n\n        print(cnt)\n\n\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13927