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} ... 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 ≤ pos ≤ |s|, c is lowercase Latin letter): replace s_{pos} with c (set s_{pos} := c); 
  * 2~ l~ r (1 ≤ l ≤ r ≤ |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 ≤ q ≤ 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
from string import ascii_lowercase
from sys import stdin


class Node:
    __slots__ = ('left', 'right', 'key', 'priority')

    def __init__(self, key, priority, left=None, right=None):
        self.left = left
        self.right = right
        self.key = key
        self.priority = priority

    def __str__(self):
        return f'{self.key}<{self.priority}> (left: {self.left}, right: {self.right})'

    def __repr__(self):
        return str(self)

    def __eq__(self, other):
        if other is not None and self.key == other.key and self.priority == other.priority:
            return self.left == other.left and self.right == other.right
        return False

    def copy(self):
        return Node(key=self.key,
                    priority=self.priority,
                    left=self.left.copy() if self.left is not None else None,
                    right=self.right.copy() if self.right is not None else None)

    def __iter__(self):
        if self.left is not None:
            yield from self.left
        yield self.key
        if self.right is not None:
            yield from self.right

    def depth(self):
        ld = 0
        if self.left:
            ld = self.left.depth()
        rd = 0
        if self.right:
            rd = self.right.depth()
        return max(ld, rd) + 1


class Treap:
    __slots__ = ('root', '_max_p', '_last', '_p', '_d')

    def __init__(self):
        self.root = None
        self._max_p = 2 ** 64 - 1
        self._last = 1

        self._p = 2 ** 65 - 49  # prime number
        self._d = self._p // 7

    def _split(self, node, key):
        """
        To split the tree by key we traverse it from its root
        to leaf putting all visited nodes into two lists: lesser nodes with keys lesser that K
        and greater nodes with keys greater (or equal to) K:

        >>> current_node = root
        >>> lesser = []
        >>> greater = []
        >>> while current_node is not None:
        >>>     if current_node.key < key:
        >>>         # current node with its left subtree goes to lesser tree
        >>>         # than we need to split right subtree of current node
        >>>         lesser.append(current_node)
        >>>         current_node = current_node.right
        >>>     else:
        >>>         # current node with its right subtree goes to greater tree
        >>>         # than we need to split left subtree of current node
        >>>         greater.append(current_node)
        >>>         current_node = current_node.left

        Lesser nodes will form the lesser tree - we need to chain them in the order they are
        present in the list, and greater nodes will form greater tree.

        Each node in lesser nodes list is right subtree of previous node in lesser nodes list,
        and each node is the root of left subtree of previous node in greater nodes list:

        >>> lesser[0].right = lesser[1]
        >>> lesser[1].right = lesser[2]
        >>> ...
        >>> greater[0].left = greater[1]
        >>> greater[1].left = greater[2]
        >>> ...

        One could explicitly build lists and then chain nodes in them, but that will
        be slightly slower than chain nodes in the same time as we traverse tree.
        """
        lesser = None
        rest = None
        lesser_node = None
        rest_node = None
        to_split = node
        while to_split is not None:
            if to_split.key < key:
                to_lesser, to_split = to_split, to_split.right
                to_lesser.right = None
                if lesser_node is None:
                    lesser = to_lesser
                else:
                    lesser_node.right = to_lesser
                lesser_node = to_lesser
            else:
                to_split, to_rest = to_split.left, to_split
                to_rest.left = None
                if rest_node is None:
                    rest = to_rest
                else:
                    rest_node.left = to_rest
                rest_node = to_rest
        return lesser, rest

    def _merge(self, lesser, greater):
        """
        Merging two trees means to traverse both of them at the same time
        and put all visited nodes into one list in some order, which depends on priorities.
        At each step of main loop we decide:
            - if lesser root has lesser priority than greater root, then lesser should become
              left subtree of greater tree, so we put node root of greater subtree to list of nodes
              and put left subtree of greater root node as new greater tree
            - otherwise we put lesser root node to list of nodes and put lesser right subtree as new
              lesser tree
            >>> nodes = []
            >>> while ...: #  while lesser or greater trees are not empty
            >>> if lesser.priority < greater.priority:  # or lesser is empty
            >>>     nodes.append(greater)
            >>>     greater = greater.left
            >>> else:
            >>>     nodes.append(lesser)
            >>>     lesser = lesser.right

        After that we just chain nodes in resulting list from end to beginning:
        if some node in list has key lesser than key of previous node, then
        node becomes left child of previous node, otherwise node becomes right child of
        previous node:
        >>> if nodes[i].key < nodes[i + 1].key:
        >>>     nodes[i].right = nodes[i + 1]
        >>> else:
        >>>     nodes[i].left = nodes[i + 1]

        We can chain nodes in the same time as we traverse lesser and greater trees,
        because at each step we need to know only two consecutive nodes of resulting list.
        """

        result = None
        current_node = None

        while lesser is not None or greater is not None:
            if lesser is None:
                add_to_tree = greater
                greater = None
            elif greater is None:
                add_to_tree = lesser
                lesser = None
            elif lesser.priority <= greater.priority:
                add_to_tree = greater
                greater = greater.left
                add_to_tree.left = None
            else:
                add_to_tree = lesser
                lesser = lesser.right
                add_to_tree.right = None

            if result is None:
                result = add_to_tree
            else:
                if current_node.key > add_to_tree.key:
                    current_node.left = add_to_tree
                else:
                    current_node.right = add_to_tree
            current_node = add_to_tree

        return result

    def __contains__(self, key):
        current_node = self.root
        while current_node is not None:
            if current_node.key < key:
                current_node = current_node.right
            elif current_node.key > key:
                current_node = current_node.left
            else:
                break
        return current_node is not None

    def insert(self, key):
        if key in self:
            return False
        self._insert(key)
        return True

    def _insert(self, key):
        """Insert _missing_ key"""
        priority = self._get_priority()

        parent = None
        current_node = self.root
        while current_node is not None and current_node.priority >= priority:
            parent = current_node
            if current_node.key < key:
                current_node = current_node.right
            else:
                current_node = current_node.left

        new_node = Node(key=key, priority=priority)

        if current_node is not None:
            new_node.left, new_node.right = self._split(current_node, key)

        if parent is None:
            self.root = new_node
        else:
            if parent.key > key:
                parent.left = new_node
            else:
                parent.right = new_node

    def _get_priority(self):
        p = (self._last * self._d) % self._p
        self._last = p
        return p

    def remove(self, key):
        if self.root is None or key not in self:
            return False
        else:
            self.root = self._remove(self.root, key)
            return True

    def successor(self, key):
        if self.root is None:
            return None
        return self._successor(self.root, key)

    def _successor(self, root, key):
        found = None
        while root is not None:
            if root.key > key:
                if found is None:
                    found = root.key
                elif root.key < found:
                    found = root.key
                root = root.left
            else:
                root = root.right
        return found

    def _remove(self, root, key, _parent=None, _where=None):
        """Remove _existing_ key"""
        parent = None
        current_node = root
        while current_node.key != key:
            parent = current_node
            if current_node.key < key:
                current_node = current_node.right
            else:
                current_node = current_node.left

        merged = self._merge(current_node.left, current_node.right)

        if parent is None:
            return merged
        elif merged is None:
            if parent.key < key:
                parent.right = None
            else:
                parent.left = None
            return root
        else:
            if parent.key > merged.key:
                parent.left = merged
            else:
                parent.right = merged
            return root

    def __iter__(self):
        if self.root is not None:
            yield from self.root

    def depth(self):
        if self.root is None:
            return 0
        else:
            return self.root.depth()


if __name__ == '__main__':
    treaps = {c: Treap() for c in ascii_lowercase}
    letters = list(stdin.readline().strip())
    for index, letter in enumerate(letters):
        treaps[letter].insert(index)

    q = int(input())
    for _ in range(q):
        query, a, b = stdin.readline().split()
        if query == '1':
            index = int(a) - 1
            old_c = letters[index]
            treaps[old_c].remove(index)
            treaps[b].insert(index)
            letters[index] = b
        else:
            start = int(a) - 1
            stop = int(b)
            counter = 0

            for c in ascii_lowercase:
                next_index = treaps[c].successor(start - 1)
                if next_index is None:
                    continue
                if start <= next_index < stop:
                    counter += 1
            print(counter)
