Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

bitmasks

data structures

dp

matrices

*2400

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. William The Oblivious

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputBefore 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 $$$s$$$ of length $$$n$$$ only consisting of characters "a", "b" and "c". There are $$$q$$$ queries of format ($$$pos, c$$$), meaning replacing the element of string $$$s$$$ at position $$$pos$$$ with character $$$c$$$. 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 $$$x$$$ is said to be a subsequence of string $$$y$$$ if $$$x$$$ can be obtained from $$$y$$$ by deleting some characters without changing the ordering of the remaining characters.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ $$$(1 \le n, q \le 10^5)$$$, the length of the string and the number of queries, respectively.

The second line contains the string $$$s$$$, consisting of characters "a", "b" and "c".

Each of the next $$$q$$$ lines contains an integer $$$i$$$ and character $$$c$$$ $$$(1 \le i \le n)$$$, index and the value of the new item in the string, respectively. It is guaranteed that character's $$$c$$$ 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

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

0 1 2 2 1 2 1 2 2 2 2 2

Note

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

- $$$s = $$$"aaaaccccc". In this case the string does not contain "abc" as a subsequence and no replacements are needed.
- $$$s = $$$"aaabccccc". In this case 1 replacements can be performed to get, for instance, string $$$s = $$$"aaaaccccc". This string does not contain "abc" as a subsequence.
- $$$s = $$$"ababccccc". In this case 2 replacements can be performed to get, for instance, string $$$s = $$$aaaaccccc". This string does not contain "abc" as a subsequence.
- $$$s = $$$"ababacccc". In this case 2 replacements can be performed to get, for instance, string $$$s = $$$"aaaaacccc". This string does not contain "abc" as a subsequence.
- $$$s = $$$"bbabacccc". In this case 1 replacements can be performed to get, for instance, string $$$s = $$$"bbacacccc". This string does not contain "abc" as a subsequence.
- $$$s = $$$"bbababccc". In this case 2 replacements can be performed to get, for instance, string $$$s = $$$"bbacacccc". This string does not contain "abc" as a subsequence.
- $$$s = $$$"bbabcbccc". In this case 1 replacements can be performed to get, for instance, string $$$s = $$$"bbcbcbccc". This string does not contain "abc" as a subsequence.
- $$$s = $$$"baabcbccc". In this case 2 replacements can be performed to get, for instance, string $$$s = $$$"bbbbcbccc". This string does not contain "abc" as a subsequence.
- $$$s = $$$"aaabcbccc". In this case 2 replacements can be performed to get, for instance, string $$$s = $$$"aaacccccc". This string does not contain "abc" as a subsequence.
- $$$s = $$$"aaababccc". In this case 2 replacements can be performed to get, for instance, string $$$s = $$$"aaacacccc". This string does not contain "abc" as a subsequence.
- $$$s = $$$"aaababccc". In this case 2 replacements can be performed to get, for instance, string $$$s = $$$"aaacacccc". This string does not contain "abc" as a subsequence.
- $$$s = $$$"aaababbcc". In this case 2 replacements can be performed to get, for instance, string $$$s = $$$"aaababbbb". This string does not contain "abc" as a subsequence.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/15/2024 12:11:47 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|