include

include

include

using namespace std;

define base 1000003

define hash_base 29

define maxn 100005

define magic 9

define hash Hash

int f[base], p[maxn * magic * magic / 2], occ[maxn * magic * magic / 2], different, ii, n, m, i, j, ps, q; long long t[maxn * magic * magic / 2], hash, stable; char a[maxn], cha;

void hashset_change (long long item, int mdf) { int q = f[abs(item) % base]; while (q) { if (t[q] == item) { if ((occ[q] > 0) != (occ[q] + mdf > 0)) different += mdf; occ[q] += mdf; return ; } q = p[q]; } ++ii; t[ii] = item; p[ii] = f[abs(item) % base]; f[abs(item) % base] = ii; occ[ii] = 1; ++different; }

int main (int argc, char * const argv[]) { scanf("%d %d\n", &n, &m); for(i = 1; i <= n; i++) { scanf("%c", &a[i]);
assert('a' <= a[i] && a[i] <= 'z'); } for(i = 1; i <= n; i++) { hash = 0; for(j = i; j <= min(i + magic - 1, n); j++) { hash = hash * hash_base + (a[j] - 'a' + 1); hashset_change(hash, 1); } stable += max(0, n - i + 1 - magic); } for(i = 1; i <= m; i++) { scanf("%d %c", &ps, &cha); for(j = max(ps - magic + 1, 1); j <= ps; j++) { hash = 0; for(q = j; q <= ps; q++) hash = hash * hash_base + (a[q] - 'a' + 1); hashset_change(hash, -1); for(q = ps + 1; q <= min(n, j + magic - 1); q++) { hash = hash * hash_base + (a[q] - 'a' + 1); hashset_change(hash, -1); } } a[ps] = cha; for(j = max(ps - magic + 1, 1); j <= ps; j++) { hash = 0; for(q = j; q <= ps; q++) hash = hash * hash_base + (a[q] - 'a' + 1); hashset_change(hash, 1); for(q = ps + 1; q <= min(n, j + magic - 1); q++) { hash = hash * hash_base + (a[q] - 'a' + 1); hashset_change(hash, 1); } } printf("%lld\n", stable + different); } return 0;

}](https://)***`[![]([https://)](https://)`*