You're given a string of characters. It's known that the string consists of lowercase Latin letters. The string is generated randomly. That means that every symbol is chosen randomly and independently from others from the set {'a', 'b', ..., 'z'}. All the letters have equal probability to appear.
You're given queries on this string. Each query is of the form P C, where is an integer between and (both inclusive) and is a character from the set {'a', 'b', ..., 'z'}. Both and were chosen at random and independently from other queries.
When you have a query of the form P C you have to change the symbol of to . After every change we ask you to output the number of distinct nonempty sub-strings of .
Input Format
The first line of input consists of two single space-separated integers and , the length of the string and the number of queries, respectively.
The second line contains string .
The following lines describe the queries in the form P C, where and are also separated with a single space.
Constraints
Output Format
Output lines. Output the number of distinct substrings of after the query on the line of the output.
Sample Input
4 4
aaab
1 a
2 b
3 c
4 d
Sample Output
7
7
9
10
Explanation
After replacing the character at the first index with a, we still have the original string aaab. The total non empty substrings of aaab are
a b aa ab aaa aab aaab
hence 7.
After replacing the character at the second index with b, we have the string abab. The non-empty substrings of abab are
a b ab ba aba bab abab
hence 7.
After replacing the character at the third index with c, we have the string abcb. The total non empty substrings of abcb are
a b c ab bc cb abc bcb abcb
hence 9.
After replacing the character at the fourth index with d, we have the string abcd. The total non empty substrings of abcd are
a b c d ab bc cd abc bcd abcd
hence 10.
Scoring
There are 12 test cases.
The first four test cases N = 100 and Q = 500
The next four test cases N = 75000 and Q = 10
The last four test cases N = 75000 and Q = 75000