You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

回文树(tree)

【题目描述】

某数据中心有一批服务器机柜，将每个机柜作为 "节点"，其排列结构恰好构成一棵按层序遍历顺次编号 1,2,…,n 的完全二叉树 。每个机柜初始都贴有一个代表运行状态的小写字母标签。

运维系统会进行 q 次远程更新操作，每次操作会修改某个指定机柜运行状态的标签字母。为了快速评估系统稳定性，每次更新后需要统计：整个机柜树中共有多少个机柜，其管辖的 "子树区域"的标签集合，能够经过重新排列形成回文串？

【输入格式】

第一行两个正整数 n, q，表示的节点数量和操作次数。

接下来一行一个长度为 n 的字符串，第 i个字符表示第 i个节点上的初始字母。

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

【输出格式】

先输出一行一个整数表示初始有几个节点，其子树内的字符集可以经过重新排列形成回文

串。

之后对于每个修改，输出一行一个整数表示当前有多少节点，其子树内的字符集可以经过重

新排列形成回文串。

【样例1 输入】

4 2

aabc

1 b

2 c

【样例1 输出】

2

2

4

【样例1 输入】

见tree2.in

【样例1 输出】

见tree2.out

​【​数据说明】