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

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:

Operation | Description | Constraints |
---|---|---|

`1 x ch` | Change the x^{th} character of S to ch (i.e. `S[x] = ch` ). | 1 ≤ x ≤ n, ‘a’ ≤ ch ≤ ‘z’ |

`2 L R ch` | Count 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’ |

The first line of the input contains two integers **n** (1 ≤ n ≤ 10^{5}) and **m** (1 ≤ m ≤ 5 × 10^{5}), 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.

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

Input | Output |
---|---|

3 4 abc 2 1 3 c 1 1 c 2 1 3 c 2 2 2 b | 1 2 1 |

85% Solution Ratio

fsshakkhorEarliest,

TurinhstuFastest, 0.1s

rafi_1703076Lightest, 1.4 MB

Riaz_BSMRSTUShortest, 801B

Login to submit