背景

民间数据

题目描述

小 C 有两个集合，分别为单词集 $D$ 和限制集 $R$，初始两个集合都是空集。

小 C 会进行 $m$ 次操作，操作分为以下两种：

• add s（其中 $s$ 是一个字符串）：表示向单词集 $D$ 中加入一个字符串 $s$。
• query s x（其中 $s$ 是一个字符串，$x$ 是一个自然数）：表示向限制集 $R$ 中加入一个限制 $(s, x)$。

一个限制 $(s, x)$ 被满足当且仅当：单词集 $D$ 中至少有 $x$ 个字符串满足 $s$ 是它们的前缀。其中，字符串 $s$ 是 $t$ 的前缀当且仅当可以通过删除 $t$ 尾部的若干个（可以是 $0$ 个）字符得到 $s$。例如，aaa 是 aaab 的前缀，也是 aaa 的前缀。

小 C 想让你告诉他：在每次操作后，限制集 $R$ 中的所有限制是否全部都被满足。

输入格式

第一行包含一个正整数 $m$ —— 表示总的操作次数。

接下来 $m$ 行，每行描述一次操作，格式为 add s 或 query s x。

输出格式

输出共 $m$ 行。对于第 $i$ 次操作，如果操作完成后限制集中的所有限制全部都被满足，则在第 $i$ 行输出 Yes；否则输出 No。

6
add a
query a 2
add ab
add ac
query ab 2
add abc

Yes
No
Yes
Yes
No
Yes

提示

样例解释

以第三次操作为例： 前三次操作完成后，$D = \{a, ab\}$，$R = \{(a, 2)\}$。 考虑 $(a, 2)$ 限制是否被满足：在集合 $D$ 中的字符串里，$a$ 是 $a$ 的前缀，$a$ 是 $ab$ 的前缀，因此恰好有 $2$ 个字符串满足条件。该限制被满足，所以输出 Yes。

其它样例说明

• 样例 $2$：见选手附加文件目录下的 string/string2.in 与 string/string2.ans。该样例满足测试点 $4 \sim 5$ 的约束条件。
• 样例 $3$：见选手附加文件目录下的 string/string3.in 与 string/string3.ans。该样例满足测试点 $9 \sim 10$ 的约束条件。

数据范围

定义 $S$ 为所有操作中给定字符串的长度之和。对于所有测试数据，保证 $m \le 10^6$，$S \le 10^6$。

各测试点的附加限制如下表所示：

• 特殊性质 $A$：所有 query 操作都在所有的 add 操作之后。
• 特殊性质 $B$：最多只有一个 query 操作。