题目描述

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

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

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

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

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

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

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

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

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

输入格式

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

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

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

输出格式

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

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

数据范围

对于 $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. 修改 $1$ 号节点为 $b$

      b
     / \
    a   b
   /
  c

依旧只有 $3,4$ 两个节点是 回文树节点

2. 修改 $2$ 号节点为 $c$

      b
     / \
    c   b
   /
  c

此时 $1,2,3,4$ 节点都是 回文树节点 $1$ 号节点的子树可以构成 $bccb$ 这个回文字符串 $2$ 号节点的子树可以构成 $cc$ 这个回文字符串 $3$ 号节点的子树可以构成 $c$ 这个回文字符串 $4$ 号节点的子树可以构成 $b$ 这个回文字符串