You are given a string $s$ consisting of lowercase Latin letters and $q$ queries for this string.

Recall that the substring $s[l; r]$ of the string $s$ is the string $s_l s_{l + 1} \dots s_r$. For example, the substrings of "codeforces" are "code", "force", "f", "for", but not "coder" and "top".

There are two types of queries:   $1~ pos~ c$ ($1 \le pos \le |s|$, $c$ is lowercase Latin letter): replace $s_{pos}$ with $c$ (set $s_{pos} := c$);  $2~ l~ r$ ($1 \le l \le r \le |s|$): calculate the number of distinct characters in the substring $s[l; r]$. 


-----Input-----

The first line of the input contains one string $s$ consisting of no more than $10^5$ lowercase Latin letters.

The second line of the input contains one integer $q$ ($1 \le q \le 10^5$) — the number of queries.

The next $q$ lines contain queries, one per line. Each query is given in the format described in the problem statement. It is guaranteed that there is at least one query of the second type.


-----Output-----

For each query of the second type print the answer for it — the number of distinct characters in the required substring in this query.


-----Examples-----
Input
abacaba
5
2 1 4
1 4 b
1 5 b
2 4 6
2 1 7

Output
3
1
2

Input
dfcbbcfeeedbaea
15
1 6 e
1 4 b
2 6 14
1 7 b
1 12 c
2 6 8
2 1 6
1 7 c
1 2 f
1 10 a
2 7 9
1 10 a
1 14 b
1 1 f
2 1 11

Output
5
2
5
2
6
[{"code": "# -*- coding: utf-8 -*-\n\nimport sys\nfrom operator import add\n\ndef input(): return sys.stdin.readline().strip()\ndef list2d(a, b, c): return [[c] * b for i in range(a)]\ndef list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]\ndef list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]\ndef ceil(x, y=1): return int(-(-x // y))\ndef INT(): return int(input())\ndef MAP(): return list(map(int, input().split()))\ndef LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]\ndef Yes(): print('Yes')\ndef No(): print('No')\ndef YES(): print('YES')\ndef NO(): print('NO')\nsys.setrecursionlimit(10 ** 9)\nINF = float('inf')\nMOD = 10 ** 9 + 7\n\nclass SegTree:\n \n    def __init__(self, n, func, init):\n\n        self.n = n\n        self.func = func\n        self.init = init\n\n        n2 = 1\n        while n2 < n:\n            n2 <<= 1\n        self.n2 = n2\n        self.tree = [self.init] * (n2 << 1)\n \n    def update(self, i, x):\n\n        i += self.n2\n        self.tree[i] = x\n        while i > 1:\n            self.tree[i >> 1] = x = self.func(x, self.tree[i ^ 1])\n            i >>= 1\n \n    def query(self, a, b):\n\n        l = a + self.n2\n        r = b + self.n2\n        s = self.init\n        while l < r:\n            if r & 1:\n                r -= 1\n                s = self.func(s, self.tree[r])\n            if l & 1:\n                s = self.func(s, self.tree[l])\n                l += 1\n            l >>= 1\n            r >>= 1\n        return s\n\nA = [ord(s)-97 for s in list(input())]\nN = len(A)\n\nst = [None] * 26\nfor i in range(26):\n    st[i] = SegTree(N, add, 0)\nfor i, a in enumerate(A):\n    st[a].update(i, 1)\n\nfor _ in range(INT()):\n    a, b, c = input().split()\n    if a == '1':\n        b = int(b)\n        cur = A[b-1]\n        nxt = ord(c) - 97\n        st[cur].update(b-1, 0)\n        st[nxt].update(b-1, 1)\n        A[b-1] = nxt\n    else:\n        b = int(b)\n        c = int(c)\n        cnt = 0\n        for i in range(26):\n            if st[i].query(b-1, c) >= 1:\n                cnt += 1\n        print(cnt)\n", "passed": true, "time": 0.77, "memory": 14368.0, "status": "done"}, {"code": "import heapq\nimport math\n\nimport sys\ninput = sys.stdin.readline\n\ndef li():return [int(i) for i in input().rstrip('\\n').split()]\ndef value():return int(input())\n\n\ndef givesum(a,b):\n    c=[0]*26\n    for i in range(len(a)):\n        c[i] = a[i]+b[i]\n    return c\ndef dolist(a):\n    c = [0]*26\n    c[ord(a)-ord('a')] = 1\n    return c\n    \nclass Node:\n    def __init__(self,s,e):\n        self.start=s\n        self.end=e\n        self.lis=[0]*26\n        self.left=None\n        self.right=None\n\ndef build(nums,l,r):\n    if l == r:\n        temp = Node(l,l)\n        # print(temp.start,ord(nums[l])-ord('a'),nums)\n        temp.lis[ord(nums[l])-ord('a')] = 1\n    else:\n        mid=(l+r)>>1\n        # print(mid,l,r)\n        temp=Node(l,r)\n        temp.left=build(nums,l,mid)\n        temp.right=build(nums,mid+1,r)\n        temp.lis=givesum(temp.left.lis,temp.right.lis)\n    return temp\n\ndef update(root,start,value):\n    if root.start==root.end==start:\n        root.lis=dolist(value)\n    elif root.start<=start and root.end>=start:\n        mid=(root.start+root.end)>>1\n        root.left=update(root.left,start,value)\n        root.right=update(root.right,start,value)\n        root.lis=givesum(root.left.lis,root.right.lis)\n    return root\n    \ndef query(root,start,end):\n    if root.start>=start and root.end<=end:return root.lis\n    elif root.start>end or root.end<start:return [0]*26;\n    else:\n        mid=(start+end)>>1\n        return givesum(query(root.left,start,end),query(root.right,start,end))\n        \ns = input().rstrip('\\n')\nroot = build(s,0,len(s)-1)\nansarun = []\n# print('arun')\nfor _ in range(int(input())):\n    templist = list(input().split())\n    if templist[0] == '1':\n        root = update(root,int(templist[1])-1,templist[2])\n    else:\n        temp1 = query(root,int(templist[1])-1,int(templist[2])-1)\n        total = 0\n        for i in temp1:\n            if i:total+=1\n        ansarun.append(total)\nfor i in ansarun:print(i)\n    \n    \n    \n    \n", "passed": true, "time": 1.51, "memory": 14384.0, "status": "done"}, {"code": "from string import ascii_lowercase as lows\nimport sys\n\ninput = sys.stdin.readline\n\nN = (1<<17)\n\nclass bit:\n    def __init__( self ):\n        self.l = [0]*(1 + N)\n    def set( self, i ):\n        self.add( i, 1 )\n    def unset( self, i ):\n        self.add( i, -1 )\n    def add( self, i, val ):\n        while i <= N:\n            self.l[ i ] += val\n            i += (i & (-i))\n    def get( self, i ):\n        r = 0\n        while i > 0:\n            r += self.l[ i ]\n            i -= (i & (-i))\n        return r\n    def range( self, l, r ):\n        return self.get( r ) - self.get( l - 1 )\n\nbits = { c: bit() for c in lows }\n\ns = [ c for c in input().strip() ]\nfor i, c in enumerate(s):\n    bits[ c ].set( i + 1 )\nq = int(input().strip())\n\nfor _ in range(q):\n    ins = input().split()\n    if ins[ 0 ] == '1':\n        pos = int( ins[ 1 ] )\n        bits[ s[ pos - 1 ] ].unset( pos )\n        bits[ ins[ 2 ] ].set( pos )\n        s[ pos - 1 ] = ins[ 2 ]\n    else:\n        l, r = list(map(int, ins[1:] ))\n        sm = 0\n        for b in list(bits.values()):\n            if b.range( l, r ) > 0:\n                sm += 1\n        print( sm )\n", "passed": true, "time": 1.57, "memory": 40016.0, "status": "done"}, {"code": "from string import ascii_lowercase as lows\nimport sys\n\ninput = sys.stdin.readline\n\ns = [ c for c in input().strip() ]\nN = len(s)\n\nclass bit:\n    def __init__( self ):\n        self.l = [0]*(1 + N)\n    def set( self, i ):\n        self.add( i, 1 )\n    def unset( self, i ):\n        self.add( i, -1 )\n    def add( self, i, val ):\n        while i <= N:\n            self.l[ i ] += val\n            i += (i & (-i))\n    def get( self, i ):\n        r = 0\n        while i > 0:\n            r += self.l[ i ]\n            i -= (i & (-i))\n        return r\n    def range( self, l, r ):\n        return self.get( r ) - self.get( l - 1 )\n\nbits = { c: bit() for c in lows }\n\nfor i, c in enumerate(s):\n    bits[ c ].set( i + 1 )\nq = int(input().strip())\n\nfor _ in range(q):\n    ins = input().split()\n    if ins[ 0 ] == '1':\n        pos = int( ins[ 1 ] )\n        bits[ s[ pos - 1 ] ].unset( pos )\n        bits[ ins[ 2 ] ].set( pos )\n        s[ pos - 1 ] = ins[ 2 ]\n    else:\n        l, r = list(map(int, ins[1:] ))\n        sm = 0\n        for b in list(bits.values()):\n            if b.range( l, r ) > 0:\n                sm += 1\n        print( sm )\n", "passed": true, "time": 0.15, "memory": 14164.0, "status": "done"}, {"code": "s=input()\nq=int(input())\nT=[]\nfor i in range(4*len(s)+10):\n    T.append(0)\n\ndef create(rt,l,r):\n    if(l==r):\n        T[rt]=1<<(ord(s[l-1])-97)\n        return\n    mid=(l+r)//2\n    create(rt<<1,l,mid)\n    create(rt<<1|1,mid+1,r)\n    T[rt]=T[rt<<1]|T[rt<<1|1]\n\ndef update(rt,l,r,pos,now):\n    if(l==r):\n        T[rt]=1<<(ord(now)-97)\n        return\n    mid=(l+r)//2\n    if(pos<=mid):\n        update(rt<<1,l,mid,pos,now)\n    else:\n        update(rt<<1|1,mid+1,r,pos,now)\n    T[rt]=T[rt<<1]|T[rt<<1|1]\n\ndef cal(rt,l,r,L,R):\n    if(l==L and R==r):\n        return T[rt]\n    mid=(l+r)//2\n    if(R<=mid):\n        return cal(rt<<1,l,mid,L,R)\n    elif(L>mid):\n        return cal(rt<<1|1,mid+1,r,L,R)\n    else:\n        return cal(rt<<1,l,mid,L,mid)|cal(rt<<1|1,mid+1,r,mid+1,R)\n\nn=len(s)\ncreate(1,1,n)\n\nfor i in range(q):\n    str=input().split()\n    if(str[0]=='1'):\n        pos=int(str[1])\n        update(1,1,n,pos,str[2])\n    else:\n        l=int(str[1])\n        r=int(str[2])\n        res=cal(1,1,n,l,r)\n        ans=0\n        while(res>0):\n            if(res%2==1):\n                ans+=1\n            res//=2\n        print(ans)", "passed": true, "time": 0.14, "memory": 14388.0, "status": "done"}, {"code": "def update(v,w,s):\n    \n    while v<=length:\n        l[s][v]+=w\n        v+=(v&(-v))\ndef get_value(v,s):\n    ans=0\n    \n    while v!=0:\n        \n        ans+=l[s][v]\n        v-=(v&(-v))\n    return ans\nfrom sys import stdin,stdout\ns=list(stdin.readline().strip())\nq=int(stdin.readline())\nlength=len(s)\nl=[[0 for i in range(length+1)] for _ in range(26)]\n\nfor i in range(length):\n    x=ord(s[i])-97\n    update(i+1,1,x)\n\nfor _ in range(q):\n    \n    n,m,k=stdin.readline().split()\n    if n=='1':\n        a=s[int(m)-1]\n        x,y=ord(a)-97,ord(k)-97\n        update(int(m),-1,x)\n        update(int(m),1,y)\n        s[int(m)-1]=k\n        \n    else:\n        count=0\n        left,r=int(m),int(k)\n        for i in range(26):\n            if get_value(r,i)-get_value(left-1,i)>=1:\n                \n                count+=1\n        print(count)\n        \n", "passed": true, "time": 0.78, "memory": 14272.0, "status": "done"}, {"code": "\nfrom sys import stdin,stdout\n\nR = lambda: map(int, input().split())\nS = list(stdin.readline().strip())\nQ = int(input())\nn = len(S)\nS = list(S)\nsum_array = [[0] * (n+1) for _ in range(26)]\n\n\ndef lowbit(x):\n    return x & -x\n\ndef add(x, val, idx):\n    while x <= n:\n        sum_array[idx][x] += val\n        x += lowbit(x)\n\ndef sum(x, idx):\n    res = 0\n    while x > 0:\n        res += sum_array[idx][x]\n        x -= lowbit(x)\n    return res\n\n\nfor i in range(n):\n    idx = ord(S[i]) - 97\n    add(i+1, 1, idx)\n\nfor _ in range(Q):\n    A = stdin.readline().split()\n    a, b, c = int(A[0]), int(A[1]), A[2]\n    if a == 1:\n        pre = ord(S[b-1]) - 97\n        cur = ord(c) - 97\n        S[b-1] = c\n        add(b, -1, pre)\n        add(b, 1, cur)\n    else:\n        c = int(c)\n        if c - b == 0:\n            print(1)\n        else:\n            res = 0\n            for i in range(26):\n                diff = sum(c, i) - sum(b-1, i)\n                res += int(diff > 0)\n            print(res)", "passed": true, "time": 0.15, "memory": 14248.0, "status": "done"}, {"code": "def update(v,w,s):\n    \n    while v<=length:\n        l[s][v]+=w\n        v+=(v&(-v))\ndef get_value(v,s):\n    ans=0\n    \n    while v!=0:\n        \n        ans+=l[s][v]\n        v-=(v&(-v))\n    return ans\nfrom sys import stdin,stdout\ns=list(stdin.readline().strip())\nq=int(stdin.readline())\nlength=len(s)\nl=[[0 for i in range(length+1)] for _ in range(26)]\n\nfor i in range(length):\n    x=ord(s[i])-97\n    update(i+1,1,x)\n\nfor _ in range(q):\n    \n    n,m,k=stdin.readline().split()\n    if n=='1':\n        a=s[int(m)-1]\n        x,y=ord(a)-97,ord(k)-97\n        update(int(m),-1,x)\n        update(int(m),1,y)\n        s[int(m)-1]=k\n        \n    else:\n        count=0\n        left,r=int(m),int(k)\n        for i in range(26):\n            if get_value(r,i)-get_value(left-1,i)>=1:\n                \n                count+=1\n        print(count)\n", "passed": true, "time": 0.77, "memory": 14380.0, "status": "done"}, {"code": "#test\ns  = list(input())\nt = [0 for i in range(len(s)*4)]\nbits = dict()\nb = 1\nfor i in range(97, 123):\n    bits[chr(i)] = b\n    b<<=1\ndef bit_repr(a):\n    return bits[a]\n\ndef popcount(i):\n    i = i - ((i >> 1) & 0x55555555)\n    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)\n    return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24\n\ndef build(A, v, t_left, t_right):\n    if t_left == t_right:\n        t[v] |= bit_repr(A[t_left])\n        return\n    left_son = (v<<1) + 1\n    right_son = left_son + 1\n    t_mid = (t_left + t_right)>>1\n    build(A, left_son, t_left, t_mid)\n    build(A, right_son, t_mid+1, t_right)\n    t[v] = t[left_son] | t[right_son]\n \ndef _update(v, t_left, t_right, index, val):\n    while t_left != t_right:\n        t_mid = (t_left + t_right)//2\n        left_son = (v<<1) + 1\n        right_son = left_son + 1\n        if index > t_mid:\n            t_left = t_mid+1\n            v = right_son\n        else:\n            t_right = t_mid\n            v = left_son\n    t[v] = bit_repr(val)\n    while v:\n        v = (v-1)>>1\n        left_son = (v<<1) + 1\n        right_son = left_son + 1\n        t[v] = t[left_son] | t[right_son]\n \ndef update(index, val):\n    _update(0, 0, len(s)-1, index-1, val)\n \ndef get_set(v, t_left, t_right, left, right):\n    if left>right:\n        return 0\n    if t_left == left and t_right == right:\n        return t[v]\n    t_mid = (t_left+t_right)>>1\n    left_son = (v<<1) + 1\n    right_son = left_son + 1\n    a = get_set(left_son, t_left, t_mid, left, min(right, t_mid))\n    b = get_set(right_son, t_mid+1, t_right, max(left, t_mid+1), right)\n    return a|b\n \ndef count(l, r):\n    return popcount(get_set(0, 0, len(s)-1, l-1, r-1))\n \ndef get_request():\n    req = iter(input().split())\n    token = int(next(req))\n    if token-1: #count\n        l, r = list(map(int, req))\n        return token, l, r\n    else:       #change\n        pos = int(next(req))\n        sym = next(req)\n        return token, pos, sym\n \ndef response(req):\n    token, a, b = req\n    if token - 1: #count\n        print(count(a,b))\n    else:\n        update(a, b)\n \n\nbuild(s,0,0,len(s)-1)\nn = int(input())\nfor i in range(n):\n    req = get_request()\n    response(req)\n", "passed": true, "time": 0.14, "memory": 14396.0, "status": "done"}, {"code": "#last solution was AC with 1965 ms\n# Test 2\ns  = list(input())\nt = [0 for i in range(len(s)*4)]\nbits = dict()\nb = 1\nfor i in range(97, 123):\n    bits[chr(i)] = b\n    b<<=1\ndef bit_repr(a):\n    return bits[a]\n\ndef popcount(i):\n    i = i - ((i >> 1) & 0x55555555)\n    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)\n    return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24\n\ndef build(A, v, t_left, t_right):\n    if t_left == t_right:\n        t[v] |= bit_repr(A[t_left])\n        return\n    left_son = (v<<1) + 1\n    right_son = left_son + 1\n    t_mid = (t_left + t_right)>>1\n    build(A, left_son, t_left, t_mid)\n    build(A, right_son, t_mid+1, t_right)\n    t[v] = t[left_son] | t[right_son]\n \ndef _update(v, t_left, t_right, index, val):\n    while t_left != t_right:\n        t_mid = (t_left + t_right)//2\n        left_son = (v<<1) + 1\n        right_son = left_son + 1\n        if index > t_mid:\n            t_left = t_mid+1\n            v = right_son\n        else:\n            t_right = t_mid\n            v = left_son\n    t[v] = bit_repr(val)\n    while v:\n        v = (v-1)>>1\n        left_son = (v<<1) + 1\n        right_son = left_son + 1\n        t[v] = t[left_son] | t[right_son]\n \ndef update(index, val):\n    _update(0, 0, len(s)-1, index-1, val)\n \ndef get_set(v, t_left, t_right, left, right):\n    if left>right:\n        return 0\n    if t_left == left and t_right == right:\n        return t[v]\n    t_mid = (t_left+t_right)>>1\n    left_son = (v<<1) + 1\n    right_son = left_son + 1\n    a = get_set(left_son, t_left, t_mid, left, min(right, t_mid))\n    b = get_set(right_son, t_mid+1, t_right, max(left, t_mid+1), right)\n    return a|b\n \ndef count(l, r):\n    return popcount(get_set(0, 0, len(s)-1, l-1, r-1))\n \ndef get_request():\n    req = iter(input().split())\n    token = int(next(req))\n    if token-1: #count\n        l, r = list(map(int, req))\n        return token, l, r\n    else:       #change\n        pos = int(next(req))\n        sym = next(req)\n        return token, pos, sym\n \ndef response(req):\n    token, a, b = req\n    if token - 1: #count\n        print(count(a,b))\n    else:\n        update(a, b)\n \n\nbuild(s,0,0,len(s)-1)\nn = int(input())\nfor i in range(n):\n    req = get_request()\n    response(req)\n", "passed": true, "time": 0.14, "memory": 14440.0, "status": "done"}, {"code": "# Test 3\n\n#basic input\ns  = input()\nn = int(input())\nt = [0 for i in range(len(s)*4)]\n\n#precalculating masks\nbits = dict()\nb = 1\nfor i in range(97, 123):\n    bits[chr(i)] = b\n    b<<=1\n\ndef bit_repr(a):\n    return bits[a]\n\ndef popcount(i):\n    i = i - ((i >> 1) & 0x55555555)\n    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)\n    return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24\n\ndef build(A, v, t_left, t_right):\n\n    if t_left == t_right:\n        t[v] |= bit_repr(A[t_left])\n        return\n\n    left_son = (v<<1) + 1\n    right_son = left_son + 1\n    t_mid = (t_left + t_right)>>1\n\n    build(A, left_son, t_left, t_mid)\n    build(A, right_son, t_mid+1, t_right)\n\n    t[v] = t[left_son] | t[right_son]\n \ndef _update(v, t_left, t_right, index, val):\n    #find destination\n    while t_left != t_right:\n        t_mid = (t_left + t_right)>>1\n        left_son = (v<<1) + 1\n        right_son = left_son + 1\n        if index > t_mid:\n            t_left = t_mid+1\n            v = right_son\n        else:\n            t_right = t_mid\n            v = left_son\n    #change val\n    t[v] = bit_repr(val)\n    #update upper nodes\n    while v:\n        v = (v-1)>>1\n        left_son = (v<<1) + 1\n        right_son = left_son + 1\n        t[v] = t[left_son] | t[right_son]\n \ndef get_set(v, t_left, t_right, left, right):\n    if left > right:\n        return 0\n    if t_left == left and t_right == right:\n        return t[v]\n    t_mid = (t_left+t_right)>>1\n    \n    left_son = (v<<1) + 1\n    right_son = left_son + 1\n\n    a = get_set(left_son, t_left, t_mid, left, min(right, t_mid))\n    b = get_set(right_son, t_mid+1, t_right, max(left, t_mid+1), right)\n\n    return a|b\n \n\n\ndef update(index, val):\n    '''Interface for _update function'''\n    _update(0, 0, len(s)-1, index-1, val)\n\ndef count(l, r):\n    '''Interface for popcount(get_set())'''\n    return popcount(get_set(0, 0, len(s)-1, l-1, r-1))\n\ndef process():\n    req = iter(input().split())\n    token = int(next(req))\n    if token-1:                     #count\n        l, r = list(map(int, req))\n        print(count(l, r))\n    else:                           #change\n        pos = int(next(req))\n        sym = next(req)\n        update(pos, sym)\n\nbuild(s, 0, 0, len(s)-1)\n\n#request - response part\nfor i in range(n):\n    process()\n", "passed": true, "time": 0.14, "memory": 14276.0, "status": "done"}, {"code": "import math\nimport bisect\nfrom functools import reduce\nimport sys\nfrom collections import defaultdict\ninput=sys.stdin.readline\ndef inn():\n    return int(input())\n \ndef inl():\n    return list(map(int, input().split()))\n \nMOD = 10**9+7\nINF = inf = 10**18+5\n \ns = list(input().strip())\nn = len(s)\nt = [[0]*26 for i in range(2*n)]\n \nfor i in range(n):\n    t[i+n][ord(s[i])-97] = 1\n \ndef build():\n    for i in range(n-1, 0, -1):\n        for j in range(26):\n            t[i][j] = t[i<<1][j] + t[i<<1|1][j]\n \ndef modify(p, val):\n    t[p+n][ord(s[p])-97] = 0\n    t[p+n][ord(val)-97] = 1\n    s[p] = val\n    p = p+n\n    while p>1:\n        for i in range(26):\n            t[p>>1][i] = t[p][i] + t[p^1][i]\n        p >>= 1\n \ndef query(l, r):\n    res = [0]*26\n    l += n\n    r += n\n    while l<r:\n        if l&1:\n            for i in range(26):\n                res[i] += t[l][i]\n            l += 1\n        if r&1:\n            r -= 1\n            for i in range(26):\n                res[i] += t[r][i]\n        l >>= 1\n        r >>= 1\n    return res\n \nbuild()\n \nfor q in range(inn()):\n    tp, l, r = input().split()\n    tp = int(tp)\n    l = int(l)\n    if tp==1:\n        modify(l-1, r)\n    elif tp==2:\n        r = int(r)\n        res = query(l-1, r)\n        c = len([i for i in range(26) if res[i]>0])\n        print(c)\n    # print(t)\n", "passed": true, "time": 0.14, "memory": 14332.0, "status": "done"}, {"code": "import sys\ninput = sys.stdin.readline\n\nS = list(input().rstrip())\nL = len(S)\nQ = int(input())\ndata = []\nfor _ in range(Q):\n    A = list(map(str, input().split()))\n    data.append(A)\n\nalp = [chr(i) for i in range(97, 97+26)]\nBITs = {}\nfor a in alp:\n    BITs[a] = [0]*(L+1)\n\ndef query_sum(i, al):\n    s = 0\n    while i > 0:\n        s += BITs[al][i]\n        i -= i & -i\n    return s\n\ndef add(i, x, al):\n    while i <= L:\n        BITs[al][i] += x\n        i += i & -i\n\ndef main():\n    for i, s in enumerate(S):\n        add(i+1, 1, s)\n\n    for A in data:\n        if A[0] == '1':\n            l, s = int(A[1]), A[2]\n            for al in alp:\n                if query_sum(l, al) - query_sum(l-1, al) == 1:\n                    add(l, -1, al)\n                    break\n            add(l, 1, s)\n        else:\n            l, r = int(A[1]), int(A[2])\n            c = 0\n            for al in alp:\n                if query_sum(r, al) - query_sum(l-1, al) > 0:\n                    c += 1\n            print(c)\n\ndef __starting_point():\n    main()\n__starting_point()", "passed": true, "time": 0.14, "memory": 14180.0, "status": "done"}, {"code": "import sys\nsys.setrecursionlimit(10**9)\ninput = sys.stdin.readline\n\n\nclass SegmentTree():\n    def __init__(self, n):\n        self.n = 2**(n-1).bit_length()\n        self.data = [0 for _ in range(2*self.n)]\n\n    def set(self, k, v):\n        v_val = ord(v)-ord('a')\n        self.data[k+self.n-1] = 1 << v_val\n\n    def build(self):\n        for k in reversed(list(range(self.n-1))):\n            self.data[k] = self.data[k*2+1] | self.data[k*2+2]\n\n    def update(self, k, a):\n        k += self.n-1\n        v_val = ord(a)-ord(\"a\")\n        self.data[k] = 1 << v_val\n\n        while k > 0:\n            k = (k-1)//2\n            self.data[k] = self.data[k*2+1] | self.data[k*2+2]\n\n    def query(self, l, r):\n        L = l+self.n\n        R = r+self.n\n        ret = 0\n        while L < R:\n            if R & 1:\n                R -= 1\n                ret |= self.data[R-1]\n            if L & 1:\n                ret |= self.data[L-1]\n                L += 1\n            L >>= 1\n            R >>= 1\n        return ret\n\n\nS = [v for v in input()[:-1]]\nN = len(S)\nQ = int(input())\nquery = [[v for v in input()[:-1].split()] for _ in range(Q)]\n\nSeg = SegmentTree(N)\nfor i, s in enumerate(S):\n    Seg.set(i, s)\n\nSeg.build()\n\nfor q, v1, v2 in query:\n    if q == \"1\":\n        Seg.update(int(v1)-1, v2)\n    else:\n        val = Seg.query(int(v1)-1, int(v2))\n        print(bin(val)[2:].count(\"1\"))\n", "passed": true, "time": 0.14, "memory": 14352.0, "status": "done"}, {"code": "import math\nimport bisect\nfrom functools import reduce\nfrom collections import defaultdict\nimport sys\ninput = sys.stdin.readline\n\ndef inn():\n    return int(input())\n\ndef inl():\n    return list(map(int, input().split()))\n\nMOD = 10**9+7\nINF = inf = 10**18+5\n\ns = list(input().strip())\nn = len(s)\nt = [[0]*26 for i in range(2*n)]\n\nfor i in range(n):\n\tt[i+n][ord(s[i])-97] = 1\n\ndef build():\n\tfor i in range(n-1, 0, -1):\n\t\tfor j in range(26):\n\t\t\tt[i][j] = t[i<<1][j] + t[i<<1|1][j]\n\ndef modify(p, val):\n\tt[p+n][ord(s[p])-97] = 0\n\tt[p+n][ord(val)-97] = 1\n\ts[p] = val\n\tp = p+n\n\twhile p>1:\n\t\tfor i in range(26):\n\t\t\tt[p>>1][i] = t[p][i] + t[p^1][i]\n\t\tp >>= 1\n\ndef query(l, r):\n\tres = [0]*26\n\tl += n\n\tr += n\n\twhile l<r:\n\t\tif l&1:\n\t\t\tfor i in range(26):\n\t\t\t\tres[i] += t[l][i]\n\t\t\tl += 1\n\t\tif r&1:\n\t\t\tr -= 1\n\t\t\tfor i in range(26):\n\t\t\t\tres[i] += t[r][i]\n\t\tl >>= 1\n\t\tr >>= 1\n\treturn res\n\nbuild()\n\nfor q in range(inn()):\n\ttp, l, r = input().split()\n\ttp = int(tp)\n\tl = int(l)\n\tif tp==1:\n\t\tmodify(l-1, r)\n\telif tp==2:\n\t\tr = int(r)\n\t\tres = query(l-1, r)\n\t\tc = len([i for i in range(26) if res[i]>0])\n\t\tprint(c)\n\t# print(t)\n", "passed": true, "time": 0.15, "memory": 14408.0, "status": "done"}, {"code": "import sys\n\ninput = sys.stdin.readline\n\nclass SegmentTree:\n    a = ord('a')\n\n    def __init__(self):\n        data = [1 << ord(c) - self.a for c in input()[:-1]]\n\n        self.n = 1 << len(bin(len(data) - 1)) - 2\n        self.data = [0] * self.n + data + [0] * (self.n - len(data))\n\n        for k in range(self.n - 1, 0, -1):\n            self.data[k] = self.data[2 * k + 1] | self.data[2 * k]\n\n    def update(self, k, c):\n        k += self.n\n        self.data[k] = 1 << ord(c) - self.a\n\n        while k > 1:\n            k >>= 1\n            self.data[k] = self.data[2 * k + 1] | self.data[2 * k]\n\n    def query(self, l, r):\n        l += self.n\n        r += self.n\n        s = self.data[r] | self.data[l]\n\n        while l < r - 1:\n            if r & 1: s |= self.data[r - 1]\n            if not l & 1: s |= self.data[l + 1]\n            l >>= 1\n            r >>= 1\n        return s\n\ntree = SegmentTree()\n\nfor i in range(int(input())):\n    q = input()[:-1].split()\n    if q[0] == \"1\":\n        tree.update(int(q[1]) - 1, q[2])\n    else:\n        s = tree.query(int(q[1]) - 1, int(q[2]) - 1)\n        print(bin(s)[2:].count(\"1\"))", "passed": true, "time": 0.16, "memory": 14192.0, "status": "done"}]