题目描述

徐老师有一棵完全二叉树，这棵树一共有 $n$ 个节点，编号为 $1 \sim n$，每个节点上有一个小写字母

其中根节点编号是 $1$，$i$ 节点的左孩子是 $i * 2$，右孩子是 $i * 2 + 1$

现在徐老师提出了一个问题，对于编号为 $i$ 的节点，如果它以及它所有子树上的字母能够组成一个回文字符串，那么徐老师就认为这个节点是 回文树节点

徐老师的算法水平不高，所以他认为，只要子树上的字母能够在任意排列的情况下成为回文字符串，那么就可以了

现在徐老师想知道这棵树有几个 回文树节点

但是石老师又给徐老师加了一个难题，他想让这道题变成一个动态的题目——增加多次修改操作

所以接下来石老师会给出 $q$ 次修改，每次修改一个节点编号为 $x$ 的节点，将这个节点上的字母修改为 $c$

在每次修改以后，石老师希望知道现在这棵树上有多少个 回文树节点

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

输入格式

本题采用文件读写。

• 读入文件名：treepoint.in
• 写出文件名：treepoint.out

输入第一行包含两个正整数 $n,q$，表示节点数量和操作次数。

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

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

输出格式

输出第一行一个整数表示一开始这棵树有几个 回文树节点

接下来 $q$ 行，每行表示在进行石老师要求的修改操作后，现在这棵树有几个 回文树节点

样例

4 2
aabc
1 b
2 c

2
2
4

数据范围与提示

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

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

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