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

题目描述

樱木花道最近接受了安西教练的特殊训练，他获得了一棵神奇的“篮球战术树”。这棵树是一棵完全二叉树，共有 $n$ 个节点，编号为 $1 \sim n$，每个节点上都标着一个小写字母，用来代表一种特殊篮球战术。😯

树的根节点编号为 $1$，每个节点 $i$ 的左孩子为 $2 \times i$，右孩子为 $2 \times i + 1$。

安西教练告诉樱木：如果一个节点及其所有子树上的字母可以重新排列形成一个回文字符串，那么这个节点就会成为“回文树节点”，意味着这种篮球战术非常稳定！😏（回文字符串是指正反读完全一样的字符串，例如 abcba 或者 xxyyxx）

然而，为了增加挑战性，安西教练还决定对这棵树进行动态调整，总共会进行 $q$ 次修改操作，每次修改将指定节点 $x$ 上的字母更改为另一个指定字母 $c$。🧐

樱木的任务是：

• 在最初以及每次修改之后，都要迅速统计当前整棵树上“回文树节点”的数量。

樱木已经彻底晕菜啦😵！快来帮他一把吧！

输入格式

第一行两个整数 $n,q$，分别表示树的节点总数和修改次数。

第二行一个长度为 $n$ 的字符串，第 $i$ 个字符表示节点 $i$ 初始的字母。

接下来 $q$ 行，每行一个整数 $x$ 和一个字符 $c$，表示将节点 $x$ 上的字母修改为 $c$。

输出格式

输出共 $q+1$ 行：

• 第一行输出最开始树上“回文树节点”的数量。
• 接下来每行输出一次修改后树上的“回文树节点”的数量。

数据范围

• 对于 $30%$ 的数据，满足 $1 \leq n,q \leq 20$
• 对于 $70%$ 的数据，满足 $1 \leq n,q \leq 1000$
• 对于 $100%$ 的数据，满足 $1 \leq n,q \leq 100000$

输入输出样例

4 2
aabc
1 b
2 c

2
2
4

样例解释

初始时树的结构如下：

      a
     / \
    a   b
   /
  c

最初只有节点 $3,4$ 是回文树节点。

• 第一次修改（节点 $1$ 改为 b）：

      b
     / \
    a   b
   /
  c

回文树节点数量依然是 $2$。

• 第二次修改（节点 $2$ 改为 c）：

      b
     / \
    c   b
   /
  c

此时节点 $1,2,3,4$ 都是回文树节点，总数为 $4$。

樱木花道，加油吧！你一定能搞定的！🔥

文件读写

• 输入文件：treepoint.in
• 输出文件：treepoint.out

限制

• 时间限制：1000ms
• 空间限制：512MB