K. 在电脑上玩游戏时偶然发现了一个奇怪的游戏。游戏包含一个初始长度为 $N$ ($1 \le N \le 1000$) 的字符串 $S$ 和一个空集合 $T$。在游戏过程中可能会发生以下事件：

• 在 $S$ 的末尾添加一个字符，从而使其长度增加 1。
• 将字符串 $S$ 加入到集合 $T$ 中。
• 游戏管理员询问：“$T$ 中有多少个字符串是 $S$ 的后缀？”。$S$ 的后缀是指可以从 $S$ 的任意位置开始、但必须在 $S$ 的最后一个位置结束的子串。

因为 K. 想去参观他家乡附近的一座著名城堡，所以你必须帮助他尽快处理这个游戏。

输入格式

输入的第一行包含两个整数：$N$（初始字符串 $S$ 的长度）和 $E$（事件的数量，$E \le 1200000$）。

第二行描述字符串 $S$；该字符串仅由小写罗马字母（a-z）组成。

接下来的 $E$ 行描述事件。这些行中的每一行都包含一个整数 $p$，描述事件类型。

• 如果 $p$ 为 1，则后面会跟一个字符（a-z），该字符将被添加到 $S$ 的末尾。
• 如果 $p$ 为 2，则将字符串 $S$ 添加到 $T$ 中。
• 如果 $p$ 为 3，则你必须回答查询：“$T$ 中有多少个字符串是当前 $S$ 的后缀？”

输出格式

输出应包含多行，对于输入中的每个类型 3 事件，输出一行，包含一个整数，表示该查询的答案。

注意：$T$ 是一个集合，因此它不包含重复元素。

注意：输入量较大：对于 C 语言推荐使用 scanf 和 printf；对于 C++，建议在读取前添加 cin.tie(NULL); ios::sync_with_stdio(false);；对于 Java，建议使用 BufferedReader 和 BufferedWriter。

样例

输入样例 1

1 11
a
2
1 b
1 a
2
2
1 c
1 a
3
1 b
1 a
3

输出样例 1

1
2

说明 1

• 最初 $S$ 为 "a"。
• 在第 1 个事件后，$T$ 变为 {"a"}。
• 在第 2 和第 3 个事件后，$S$ 变为 "aba"。
• 在第 4 个事件后，$T$ 变为 {"a", "aba"}。
• 在第 5 个事件后，$T$ 变为 {"a", "aba"}。
• 在第 6 和第 7 个事件后，$S$ 变为 "abaca"。
• 查询的结果为 1（"a"）。
• 在第 9 和第 10 个事件后，$S$ 变为 "abacaba"。
• 查询的结果为 2（"a" 和 "aba"）。