题目描述

在观星台，一位友好的绿翔给炼金师带来了大量的「细胞」。炼金师客气地将这些发蓝光的小球尽数收下，并把他请回了下水道。

现在，炼金师要用这些「细胞」开始他的万灵药实验。

每个细胞都残留有一段 $DNA$ 序列，我们不妨把这些序列用仅包含字母 ‘ $abcd$ ’ 的字符串来表示。

炼金师惊讶地发现，这些细胞的 $DNA$ 序列都是某个大的 $DNA$ 序列 $S$ 的子串（这个大的 $DNA$ 序列隐藏着什么秘密呢？难道和最早使用「细胞」的月神族有关？...）。

不仅如此，由于绿翔先生使用了一些较为粗糙的近战武...... 额不，细胞收集器，导致所有细胞的 $DNA$ 序列都是 $S$ 的某两个前缀 $x$ 和 $y$ 的最长公共后缀（注意 $x$ 和 $y$ 可以相同）。 一个配方的亲和指数等于配方里所有细胞的不同 $DNA$ 序列两两之间的最长公共前缀的长度之和。炼金师正在配置一个配方，他希望研究配方的亲和指数对万灵药药效的影响。

初始时配方是空的。每一次，炼金师会将含有某个 $DNA$ 序列的细胞加入配方，或者将含有某个 $DNA$ 序列的细胞从配方中删去。你需要在他的每次操作后，快速地告诉他这个配方的亲和指数。

输入格式

第一行包含一个字符串 $S$ ，含义见题目描述，保证仅由小写英文字母 ‘ $abcd$ ’ 组成；

第二行包含一个整数 $Q$ 表示操作次数；

接下来 $Q$ 行，每行两个正整数 $x, y$ ，记 $s_{xy}$ 表示字符串 $S$ 长度为 $x$ 的前缀和长度为 $y$ 的前缀的最长公共后缀。若配方中没有含 $s_{xy}$ 的细胞，则把含 $s_{xy}$ 的细胞加入配方，否则将所有含 $s_{xy}$ 的细胞从配方中移除。

输出格式

对于每次操作，输出一行一个整数，表示操作执行后配方的亲和指数。

数据范围

对于所有测试点： $|S|, Q \le 5 \times 10^5$ 。

每个测试点的具体限制见下表：

提示：第一次操作后，答案一定是 $0$ 。

输入样例 1

bcaccb
5
2 2
1 6
5 5
5 2
1 1

输出样例 1

0
1
4
4
2

样例解释

第一次操作后配方中的 $DNA$ 序列： $\{bc\}$ ； 第二次操作后： $\{bc, b\}$ ； 第三次操作后： $\{bc, b, bcacc\}$ ； 第四次操作后： $\{bc, b, bcacc, c\}$ ； 第五次操作后： $\{bc, bcacc, c\}$ 。