该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

某大家族修缮祖祠时整理出一套传家印。族谱共记载了 $n$ 位成员，编号 $1 \sim n$，每位成员都传下一枚印章，印章上刻着一个小写字母。

族谱按如下规则编排：先祖编号为 $1$；编号为 $i$ 的成员，其两房子女分别登记在编号 $2i$ 与 $2i+1$（若某房编号超过 $n$，则该房无记载）。

族谱研究馆提出"圆满支系"的说法：对于编号为 $i$ 的成员，如果把他本人连同他所有后代身上的印章收集起来，这些字母在任意排列的情况下能够组成一个回文字符串，就称 $i$ 是一个圆满支系的始祖。

研究馆想知道这套族谱里共有多少位圆满支系的始祖。

修复团队随后入驻：他们将对印章进行 $q$ 次修复，每次把编号为 $x$ 的成员的印章重新刻为字母 $c$（覆盖原来的字母）。

每次修复之后，研究馆都希望知道当前共有多少位圆满支系的始祖。

P.S. 回文字符串是指从左往右念和从右往左念一样的字符串，比如 abcba,aaeebeeaa,xxyyxx

输入格式

输入第一行包含两个正整数 $n,q$，表示成员数量和修复次数。

接下来一行一个长度为 $n$ 的字符串，第 $i$ 个字符表示编号为 $i$ 的成员印章上的初始字母。

接下来 $q$ 行，每行一个正整数 $x$ 和一个小写字母 $c$，表示把编号为 $x$ 的成员的印章重新刻为 $c$。

输出格式

输出第一行一个整数，表示一开始共有多少位圆满支系的始祖

接下来 $q$ 行，每行一个整数，表示每次修复后当前共有多少位圆满支系的始祖

数据范围

对于 $100\%$ 的数据，满足 $1 \leq n,q \leq 100000$

输入样例

7 2
aabcbca
7 b
1 c

输出样例

5
6
5

样例解释

族谱一开始是这样的：

        a(1)
       /      \
     a(2)     b(3)
    /    \    /    \
  c(4)  b(5) c(6)  a(7)

一开始，$4,5,6,7$ 号成员的支系各只有一个字母，自然是回文；$1$ 号支系的七个字母能排成 $abcacba$ 这样的回文字符串；而 $2$ 号支系与 $3$ 号支系的字母都无法排成回文字符串。所以一开始共有 $5$ 位圆满支系的始祖。

1. 修复 $7$ 号印章为 $b$

        a(1)
       /      \
     a(2)     b(3)
    /    \    /    \
  c(4)  b(5) c(6)  b(7)

$3$ 号支系的字母 $b,c,b$ 能排成 $bcb$，$1$ 号支系的字母仍能排成回文字符串（如 $abcbcba$），此时共有 $6$ 位圆满支系的始祖

2. 修复 $1$ 号印章为 $c$

        c(1)
       /      \
     a(2)     b(3)
    /    \    /    \
  c(4)  b(5) c(6)  b(7)

$1$ 号支系的字母变为 $a,b,b,b,c,c,c$，无法排成回文字符串，此时共有 $5$ 位圆满支系的始祖