题目背景

一分钟后的出题人阻止了这个时刻的出题人写一个有趣的题目背景。

（题目背景图片来自 Phigros 曲绘，如有侵权，请告知出题人。）

题目描述

给你一个字符串 $S$，设 $S=\overline{s_1s_2\dots s_n}$。

有一个字符串 $T$，初始时 $T=S$，你可以进行若干次操作，每次操作可以选取 $S$ 一个子串并插入到 $T$ 的任意位置。

你希望经过若干次操作后，$T=\overline{s_1s_1s_2s_2\dots s_ns_n}$，定义 $f(S)$ 为满足此条件所需的最少的操作次数。

此外，字符串 $S$ 还会发生一些改变。具体地，有 $q$ 次修改操作，每次修改操作会给出 $p$ 和 $\texttt{c}$，表示令 $s_p\gets \texttt{c}$。$\texttt{c}$ 表示任意一个小写字母，而并非 ASCII 为 $99$ 的字符。

你需要在最开始和每次修改后求出 $f(S)$ 的值。

输入格式

第一行一个整数 $q$ 表示修改次数。
第二行仅由小写字母构成的字符串 $S$。
接下来 $q$ 行，每行一个整数 $p$ 和一个小写字母 $\texttt{c}$ 表示一次修改。

输出格式

共有 $q+1$ 行，每行一个整数表示答案。

2
aabc
2 b
4 b

2
2
1

提示

Idea：cyffff，Solution：cyffff，Code：cyffff，Data：cyffff

Clock Paradox - WyvernP (Insane12.6)

本题输入输出文件较大，请使用恰当的输入输出方式。

提示

称字符串 $A$ 是字符串 $S$ 的子串当且仅当存在 $1\le l\le r\le |S|$ 使得 $A=\overline{s_ls_{l+1}\dots s_{r}}$。

样例解释

所有修改前，$f(S)$ 的计算方法如下：

初始时，$S=T=\texttt{aabc}$。

第一次操作，选取 $S$ 的子串 $\texttt{aa}$，插入到 $T$ 的最前端，操作后 $T=\texttt{aaaabc}$。

第二次操作，选取 $S$ 的子串 $\texttt{bc}$，插入到 $T$ 的第 $5$ 个字符后，操作后 $T=\texttt{aaaabbcc}$，符合要求。

经过一次修改、两次修改后的 $S$ 分别等于 $\texttt{abbc}$ 和 $\texttt{abbb}$，这两次修改后 $f(S)$ 分别是 $2$ 和 $1$。

数据规模

本题采用捆绑测试。 | $\text{Subtask}$ | $\vert S\vert\le$ | $q\le$ | $\text{Score}$ | | :----------: | :----------: | :----------: | :----------: | | $1$ | $5$ | $0$ | $10$ | | $2$ | $10^4$ | $10^4$ | $20$ | | $3$ | $5\times10^5$ | $0$ | $20$ | | $4$ | $5\times10^5$ | $5\times 10^5$ | $20$ | | $5$ | $3\times10^6$ | $3\times 10^6$ | $30$ |

对于 $100\%$ 的数据，$1\le|S|\le3\times10^6$，$0\le q\le 3\times10^6$，保证 $S$ 仅由小写字母构成，保证 $\texttt{c}$ 为单个小写字母。