← 返回题目列表

Codeforces · 163/E

E. 电子政务

中文机器翻译题面 查看原题

Embezzland 最好的程序员竞相开发名为“电子政务”的项目的一部分——自动统计收集和新闻分析系统。

我们知道 k 名公民中的任何一个都可以成为 Embezzland 政府的成员。公民的姓氏为a1、a2、...、ak。所有的姓氏都不同。最初,该列表中的所有 k 个公民都是政府成员。系统应支持以下选项:

- 将公民人工智能纳入政府。
- 将公民人工智能排除在政府之外。
- 给定报纸文章文本,计算它的政治化程度。为此,对于每个活跃的政府成员,系统都会将其姓氏作为子字符串在文本中出现的次数进行计数。所有发生的事件都被考虑在内,包括相交的事件。文本的政治化程度定义为所有活跃政府成员的这些值的总和。

实施该系统。

输入

第一行包含空格分隔的整数 n 和 k (1 ≤ n, k ≤ 105) — 系统查询的数量和潜在政府成员的数量。

接下来的 k 行包含姓氏 a1, a2, ..., ak,每行一个。所有姓氏都是成对不同的。

接下来的 n 行包含对系统的查询,每行一个。每个查询由一个确定操作的字符和操作参数组成,连续写入且不带空格。

操作“纳入政府”对应于字符“+”,操作“排除”对应于字符“-”。这些操作的参数是 1 到 k 之间的整数——参与操作的公民的索引。任何公民都可以以任何顺序任意次数地被纳入政府或被排除在政府之外。将已经在政府的公民纳入政府或将不在政府的公民排除在外都不会改变任何事情。

操作“计算政治化”对应字符“?”。它的论点是一个文本。

所有字符串(姓氏和文本)都是小写拉丁字母的非空序列。所有姓氏总长度不超过106,所有文本总长度不超过106。

输出

对于任何“计算政治化”操作,请在单独的行上打印给定文本的政治化程度。对于其他操作不打印任何内容。

示例

输入 #1

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

输出 #1

6
4
3
6