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 xth 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 ≤ 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.
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 |