题目描述

小 P 有一棵以数组方式存储的二叉树，共 $n$ 个节点，编号 $1 \sim n$，其中 $1$ 号节点为根。对于节点 $i$，若 $2i \leq n$ 则其左儿子为节点 $2i$，若 $2i+1 \leq n$ 则其右儿子为节点 $2i+1$。每个节点上写有一个小写字母。

称一个节点为回文节点，当且仅当该节点子树中所有节点上的字母能够重新排列成一个回文串。例如，字母集合 $\{a, a, b\}$ 可以排列成 aba，是回文串；而 $\{a, b, c\}$ 无论怎样排列都不是回文串。

小 P 想知道这棵树中有多少个回文节点。此后还会有 $q$ 次修改操作，每次将某个节点上的字母改为指定字母。需要在初始时以及每次修改后，分别回答当前树中回文节点的数量。

输入格式

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

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

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

输出格式

第一行一个整数，表示初始时回文节点的数量。

接下来 $q$ 行，每行一个整数，表示经过对应修改操作后回文节点的数量。

样例

样例 1 输入

5 2
abaca
4 b
2 c

样例 1 输出

3
5
3

样例解释

初始时树的结构如下（括号内为节点编号）：

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

节点 $3$、$4$、$5$ 的子树各只有一个字母，都是回文节点。节点 $2$ 的子树字母为 $\{b, c, a\}$，三种字母各出现一次，无法排成回文串。节点 $1$ 的子树字母为 $\{a, a, a, b, c\}$，$a$ 出现三次、$b$ 和 $c$ 各一次，也无法排成回文串。初始答案为 $3$。

将节点 $4$ 改为 $b$ 后，节点 $2$ 的子树字母变为 $\{b, b, a\}$，节点 $1$ 的子树字母变为 $\{a, a, a, b, b\}$，均能排成回文串，答案变为 $5$。

再将节点 $2$ 改为 $c$ 后，节点 $2$ 的子树字母变为 $\{c, b, a\}$，节点 $1$ 的子树字母变为 $\{a, a, a, c, b\}$，又无法排成回文串，答案变回 $3$。

附加样例

样例 2 见 ex_palintree2.in 和 ex_palintree2.ans。

数据范围

对于所有数据：$1 \leq n \leq 10^5$，$0 \leq q \leq 10^5$，$1 \leq x \leq n$，$c$ 为小写字母。

本题采用捆绑测试。只有通过一个子任务的全部测试，才能获得该子任务的分数。