William The Oblivious solution codeforces

William The Oblivious solution codeforces

Before becoming a successful trader William got a university degree. During his education an interesting situation happened, after which William started to listen to homework assignments much more attentively. What follows is a formal description of the homework assignment as William heard it:

You are given a string ss of length nn only consisting of characters “a“, “b” and “c“. There are qq queries of format (pos,cpos,c), meaning replacing the element of string ss at position pospos with character cc. After each query you must output the minimal number of characters in the string, which have to be replaced, so that the string doesn’t contain string “abc” as a subsequence. A valid replacement of a character is replacing it with “a“, “b” or “c“.

A string xx is said to be a subsequence of string yy if xx can be obtained from yy by deleting some characters without changing the ordering of the remaining characters.

Input

The first line contains two integers nn and qq (1n,q105)(1≤n,q≤105), the length of the string and the number of queries, respectively.

The second line contains the string ss, consisting of characters “a“, “b” and “c“.

Each of the next qq lines contains an integer ii and character cc (1in)(1≤i≤n), index and the value of the new item in the string, respectively. It is guaranteed that character’s cc value is “a“, “b” or “c“.

Output

For each query output the minimal number of characters that would have to be replaced so that the string doesn’t contain “abc” as a subsequence.

Example
input

Copy
9 12
aaabccccc
4 a
4 b
2 b
5 a
1 b
6 b
5 c
2 a
1 a
5 a
6 b
7 b
output

Copy
0
1
2
2
1
2
1
2
2
2
2
2
Note

Let’s consider the state of the string after each query:

  1. s=s=aaaaccccc“. In this case the string does not contain “abc” as a subsequence and no replacements are needed.
  2. s=s=aaabccccc“. In this case 1 replacements can be performed to get, for instance, string s=s=aaaaccccc“. This string does not contain “abc” as a subsequence.
  3. s=s=ababccccc“. In this case 2 replacements can be performed to get, for instance, string s=s=aaaaccccc“. This string does not contain “abc” as a subsequence.
  4. s=s=ababacccc“. In this case 2 replacements can be performed to get, for instance, string s=s=aaaaacccc“. This string does not contain “abc” as a subsequence.
  5. s=s=bbabacccc“. In this case 1 replacements can be performed to get, for instance, string s=s=bbacacccc“. This string does not contain “abc” as a subsequence.
  6. s=s=bbababccc“. In this case 2 replacements can be performed to get, for instance, string s=s=bbacacccc“. This string does not contain “abc” as a subsequence.
  7. s=s=bbabcbccc“. In this case 1 replacements can be performed to get, for instance, string s=s=bbcbcbccc“. This string does not contain “abc” as a subsequence.
  8. s=s=baabcbccc“. In this case 2 replacements can be performed to get, for instance, string s=s=bbbbcbccc“. This string does not contain “abc” as a subsequence.
  9. s=s=aaabcbccc“. In this case 2 replacements can be performed to get, for instance, string s=s=aaacccccc“. This string does not contain “abc” as a subsequence.
  10. s=s=aaababccc“. In this case 2 replacements can be performed to get, for instance, string s=s=aaacacccc“. This string does not contain “abc” as a subsequence.
  11. s=s=aaababccc“. In this case 2 replacements can be performed to get, for instance, string s=s=aaacacccc“. This string does not contain “abc” as a subsequence.
  12. s=s=aaababbcc“. In this case 2 replacements can be performed to get, for instance, string s=s=aaababbbb“. This string does not contain “abc” as a subsequence.
  13. For Solution

    Click Here!

Leave a Comment

Your email address will not be published. Required fields are marked *