您正在设计一个时髦的新文本编辑器,并且想要添加一个漂亮的自动完成功能来帮助用户节省时间。它的工作原理如下:如果用户输入“App”,您的编辑器会神奇地建议单词“Application”!更好的是,用户可以个性化编辑器中自动完成的单词。
你的编辑器将支持4种操作(假设你的编辑器中当前的文本是$$$t$$$):
1. 添加自动完成模式$$$p_i$$$。
2. 删除自动完成模式$$$p_i$$$。
3. 将字符串 $$$s$$$ 附加到 $$$t$$$ 的末尾。
4. 删除$$$t$$$末尾的$$$c$$$字符。请注意,如果 $$$c$$$ 大于 $$$t$$$ 的长度,则删除 $$$t$$$ 中的所有字符。
在每个操作之后,您的编辑应该建议一个符合以下条件的自动完成候选 $$$i$$$:
1. 字符串$$$p_i$$$ 的前缀等于$$$t$$$。
2. 如果有多个$$$p_i$$$,则选择最长的一个。
3. 如果还有多个$$$p_i$$$,则选择字典顺序最小的一个。
4. 如果还有多个$$$p_i$$$,则选择ID最小的一个。
例如,假设我们有三个候选:“alice”、“bob”和“charlie”,ID 分别为 1、2 和 3。起初,屏幕上没有任何内容,因此应建议“charlie”(3),因为它最长。然后,假设用户输入“b”。您应该建议“bob”(2),因为它是唯一以“b”开头的。最后,假设用户输入“body”。您应该打印 -1,因为没有匹配的模式。
输入
第一行包含一个整数 $$$n$$$,后面是 $$$n$$$ 行,每行包含一个操作。
有四种类型的操作:
1.$$$i$$$$$$p_i$$$
2.$$$i$$$
3.$$$s$$$
4.$$$c$$$
- $$$1 \leq n \leq 10^6$$$
- 所有 $$$p_i$$$ 和 $$$s$$$ 中的字符总数不超过 $$$2\times 10^6$$$。
- $$$1 \leq c \leq 2\times 10^6$$$
- 字符串 $$$p_i$$$ 和 $$$s$$$ 可以包含任何可打印字符,但不包括所有空格字符(范围从 $$$33$$$ 到 $$$126$$$ 的 ASCII 数字)。
- 每个添加操作的 ID $$$i$$$ 都是唯一的。
- 每次删除的 ID $$$i$$$ 保证有效。
- 每个 ID $$$i$$$ 满足 $$$0\le i \le n$$$。
输出
程序应输出 $$$n$$$ 行。对于每个操作,输出一个整数 $$$i$$$,这意味着在该操作之后,$$$p_i$$$ 是建议的自动完成候选者。如果没有符合要求的$$$p_i$$$,则输出-1。
示例
输入 #1
6 add 1 pattern1_alice add 2 pattern2_bob add 3 pattern3_charlie append pattern append 2_bobabc backspace 3
输出 #1
1 1 3 3 -1 2
输入 #2
6 append pattern add 1 pattern1_alice____ add 2 pattern2_bob______ add 3 pattern3_charlie__ delete 1 delete 2
输出 #2
-1 1 1 1 2 3