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.

Sample

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

Submit

Login to submit.

Statistics

86% Solution Ratio
fsshakkhorEarliest, Apr '19
Eleus_AhammadFastest, 0.1s
rafi_1703076Lightest, 1.4 MB
steinumShortest, 686B
Toph uses cookies. By continuing you agree to our Cookie Policy.