e-Government

题意翻译

给定包含k个字符串的集合S，有n个操作，操作有三种类型： 以‘？’开头的操作为询问操作，询问当前字符串集S中的每一个字符串匹配询问字符串的次数之和； 以‘+’开头的操作为添加操作，表示将编号为i的字符串加入到集合中； 以‘-’开头的操作为删除操作，表示将编号为i的字符串从集合中删除。 注意当编号为i的字符串已经在集合中时，允许存在添加编号为i的字符串，删除亦然。

题目描述

The best programmers of Embezzland compete to develop a part of the project called "e-Government" — the system of automated statistic collecting and press analysis. We know that any of the $ k $ citizens can become a member of the Embezzland government. The citizens' surnames are $ a_{1},a_{2},...,a_{k} $ . All surnames are different. Initially all $ k $ citizens from this list are members of the government. The system should support the following options: - Include citizen $ a_{i} $ to the government. - Exclude citizen $ a_{i} $ from the government. - Given a newspaper article text, calculate how politicized it is. To do this, for every active government member the system counts the number of times his surname occurs in the text as a substring. All occurrences are taken into consideration, including the intersecting ones. The degree of politicization of a text is defined as the sum of these values for all active government members. Implement this system.

输入输出格式

输入格式

The first line contains space-separated integers $ n $ and $ k $ ( $ 1<=n,k<=10^{5} $ ) — the number of queries to the system and the number of potential government members. Next $ k $ lines contain the surnames $ a_{1},a_{2},...,a_{k} $ , one per line. All surnames are pairwise different. Next $ n $ lines contain queries to the system, one per line. Each query consists of a character that determines an operation and the operation argument, written consecutively without a space. Operation "include in the government" corresponds to the character "+", operation "exclude" corresponds to "-". An argument of those operations is an integer between $ 1 $ and $ k $ — the index of the citizen involved in the operation. Any citizen can be included and excluded from the government an arbitrary number of times in any order. Including in the government a citizen who is already there or excluding the citizen who isn't there changes nothing. The operation "calculate politicization" corresponds to character "?". Its argument is a text. All strings — surnames and texts — are non-empty sequences of lowercase Latin letters. The total length of all surnames doesn't exceed $ 10^{6} $ , the total length of all texts doesn't exceed $ 10^{6} $ .

输出格式

For any "calculate politicization" operation print on a separate line the degree of the politicization of the given text. Print nothing for other operations.

输入输出样例

输入样例 #1

7 3
a
aa
ab
?aaab
-2
?aaab
-3
?aaab
+2
?aabbaa

输出样例 #1

6
4
3
6