时间限制： 2.5 秒

空间限制： 512 MB

题目描述

给定一个允许重复的字符串集合 $S$，你需要执行两种不同的操作。

• 加入操作

  • 指令格式为 ADD <string> <int>。其中 <string> 为一个待录入的字符串，<int> 为一个介于 $1$ 和 <string> 字符串长度之间的正整数。
  • 你需要将录入字符串 <string> 中所有长度为 <int> 的连续子串加入集合 $S$。
  • 例如：ADD aaab 2 表示将分割后的子串结果 $\{aa, aa,ab\}$ 全部加入集合 $S$ 中。

• 查询操作

  • 指令格式为 QUERY <string> <string>。其中前一个 <string> 为起始查询字符串，后一个 <string> 为终止查询字符串。你需要返回一个整数，代表集合 $S$ 中字典序介于起始查询字符串和终止查询字符串之间（包括起始和终止查询字符串）的字符串个数。

输入格式

从标准输入读入数据。

输入的第一行为一个正整数 $n$，表示指令行数。

接下来 $n$ 行，每行为一个指令，格式见【题目描述】。

输出格式

输出到标准输出。

输出若干行，每行一个整数，先后对应每次查询操作返回的结果。

4
ADD aaab 2
QUERY aa ab
ADD abc 1
QUERY a b

3
5

样例 1 解释

执行第一个指令后，$S=\{aa,aa,ab\}$。

执行第二个指令，有 $3$ 个元素满足条件。

执行第三个指令，$S=\{a,aa,aa,ab,b,c\}$。

执行第四个指令，有 $5$ 个元素满足条件。

子任务

设单个测试数据中所有录入字符串和查询字符串的长总和为 $\sum |\text{str}|$，对于所有数据，保证：

• $1\le n\le \sum |\text{str}|\le 10^6$；
• 所有录入字符串和查询字符串仅包含小写字母；
• 每次插入操作输入的数字长度在 $1$ 到录入字符串长度之间（包括边界）。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

• 子任务 1（20 分）：保证 $\sum |\text{str}|\le 5\times 10^3$；
• 子任务 2（30 分）：保证 $\sum |\text{str}|\le 2\times 10^5$，且字符串集合 $S$ 中的所有字符串长度均不大于 $50$；
• 子任务 3（30 分）：保证 $\sum |\text{str}|\le 2\times 10^5$；
• 子任务 4（20 分）：无特殊限制。