Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Another Query on String

Limits: 1s, 512 MB

You are given a string S (of length n) consisting of alphabets only. You need to perform m queries on the string.

In each query, there will be one of the two types of operations. They are as follow:

OperationDescriptionConstraints
1 x chChange the xth character of S to ch (i.e. S[x] = ch).1 ≤ x ≤ n, ‘a’ ≤ ch ≤ ‘z’
2 L R chCount the number of occurrences of ch between indices L and R in S. That means, you have to count number of such indices i where S[i] == ch.L ≤ i ≤ R, L ≤ R ≤ n, ‘a’ ≤ ch ≤ ‘z’

Input

The first line of the input contains two integers n (1 ≤ n ≤ 105) and m (1 ≤ m ≤ 5 × 105), the length of the string S and the number of queries respectively.

The next line will contain the string S.

Each of the next m lines will contain any type of the two operations mentioned in the description.

Output

You don’t need to print anything for the first type of query. Print the desired answer for the second type.

Samples

InputOutput
3 4
abc
2 1 3 c
1 1 c
2 1 3 c
2 2 2 b
1
2
1

Discussion