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 = "# coding: utf-8\nimport sys\n#from operator import itemgetter\nsysread = sys.stdin.readline\n#from heapq import heappop, heappush\nfrom collections import defaultdict\n#from itertools import combinations\nsys.setrecursionlimit(10**7)\nimport math\nclass SegTree():\n    '''\n    input idx: 1-\n    '''\n    def __init__(self, n, init_val=0):\n        self.n = n\n        self.init_val = init_val\n        self.n_leaf = 2 ** math.ceil(math.log2(n))\n        self.bins = [init_val] * (self.n_leaf * 2)\n\n    def val_append(self, A):\n        '''\n        :param A:\n        :return:\n        '''\n        if len(A) != self.n:\n            raise ValueError('The number of input should be same with n_leaf')\n        for i,a in enumerate(A):\n            self.bins[self.n_leaf+i]=a\n        self._calc()\n        return None\n\n    def _calc(self):\n        '''\n        Calculate all bins based on values of leaves\n        '''\n        i = self.n_leaf - 1\n        while i > 0:\n            self.bins[i] = self._criteria(self.bins[i*2], self.bins[i*2+1])\n            i -= 1\n        return None\n\n    def _criteria(self, x, y):\n        '''\n        Define criteria between 2 nodes\n        '''\n        return x | y\n\n    def eval_between(self, x, y):\n        '''\n        x, y : node-idx(1-)\n        '''\n        l, r = x + self.n_leaf - 1, y + self.n_leaf - 1\n        ret = self._criteria(self.bins[l], self.bins[r])\n        while l < r:\n            if l % 2 == 1:\n                ret = self._criteria(self.bins[l], ret)\n                l += 1\n                continue\n\n            if r % 2 == 0:\n                ret = self._criteria(self.bins[r], ret)\n                r -= 1\n                continue\n            l = l//2\n            r = r//2\n            ret = self._criteria(self.bins[l], ret)\n            ret = self._criteria(self.bins[r], ret)\n\n        return ret\n\n    def update(self, node, pro):\n        '''\n        Replacement of the value in a leaf\n        '''\n        current = node + self.n_leaf - 1\n        self.bins[current] = pro\n        current //= 2\n        while current > 0:\n            self.bins[current] = self._criteria(self.bins[current*2+1], self.bins[current*2])\n            current //= 2\n        return None\n\ndef run():\n    N = int(input())\n    S = list(input())\n    Q = int(input())\n    queries = [sysread().split() for _ in range(Q)]\n\n    bins = [0] * N# a: ord('a') - 97\n    for i,s in enumerate(S):\n        id = ord(s) - 97\n        bins[i] = 1<<id\n\n    segtree = SegTree(N)\n    segtree.val_append(bins)\n\n    for type, i,c in queries:\n        if type == '1':\n            c = 1 << (ord(c) - 97)\n            segtree.update(int(i), c)\n        else:\n            i,c = int(i), int(c)\n            tmp = segtree.eval_between(i,c)\n            print(bin(tmp).count('1'))\n\ndef __starting_point():\n    run()\n__starting_point()"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 18695