Description

现在给你一个按层序遍历顺次编号1,2, . . . , n的完全二叉树。初始时， 二叉树上每个节点初始 都有一个字母。

接下来会有q次操作，每次操作修改一个节点上的字母。 你需要回答每次修改完成后， 二叉树上有多少节点， 其子树内的字符集可以经过重新排列形 成回文串。

保证所有出现的字母均为小写字母。

Input Format

第一行两个正整数 n, q ，表示完全二叉树的节点数量和操作次数。 接下来一行一个长度为 n 的字符串， 第 i 个字符表示第 i 个节点上的初始字母。 接下来 q 行，每行一个正整数 x 一个字符 ch，表示将节点 x 上的字母修改为 ch。

Output Format

先输出一行一个整数表示初始有几个节点，其子树内的字符集可以经过重新排列形成回文 串。 之后对于每个修改， 输出一行一个整数表示当前有多少节点， 其子树内的字符集可以经过重 新排列形成回文串。

4 2
aabc
1 b
2 c

2
2
4

Hint

数据范围