I. 自动补全
时间限制：每个测试点 4 秒
内存限制：每个测试点 1024 MB

---

题目描述

你正在设计一款时髦的新文本编辑器，想要添加一个便捷的自动补全功能来帮助用户节省时间。其工作方式如下：如果用户输入 "App"，编辑器会神奇地建议单词 "Application"！更棒的是，用户还可以在编辑器中个性化设置自动补全的单词。

编辑器支持 4 种操作（设编辑器中的当前文本为 $t$）：

1. 添加一个自动补全模式 $p_i$。
2. 删除一个自动补全模式 $p_i$。
3. 追加一个字符串 $s$ 到 $t$ 的末尾。
4. 删除 $c$ 个字符从 $t$ 的末尾。注意：如果 $c$ 大于 $t$ 的长度，则删除 $t$ 中的所有字符。

每次操作后，编辑器应建议一个满足以下条件的自动补全候选项 $i$：

• 字符串 $p_i$ 的前缀等于 $t$；
• 如果有多个 $p_i$，选择最长的那个；
• 如果仍有多个，选择字典序最小的那个；
• 如果仍有多个，选择 ID 最小 的那个。

为简化问题，每次操作后输出建议的自动补全模式 ID。如果没有匹配，输出 $-1$。

---

示例

假设有三个候选项："alice"、"bob"、"charlie"，ID 分别为 $1$、$2$、$3$。
初始时屏幕为空，因此建议 "charlie"（$3$），因为它最长。
接着用户输入 "b"，建议 "bob"（$2$），因为它是唯一以 "b" 开头的。
最后用户输入 "body"，输出 $-1$，因为没有匹配的模式。

---

输入格式

第一行包含一个整数 $n$，接下来 $n$ 行，每行包含一个操作。

共有四种操作类型：

• add i pi
• delete i
• append s
• backspace c

参数之间由单个空格分隔。

数据范围：

• $1 \le n \le 10^6$
• 所有 $p_i$ 和 $s$ 的字符总数不超过 $2 \times 10^6$
• $1 \le c \le 2 \times 10^6$
• $p_i$ 和 $s$ 可包含任意可打印字符（ASCII 33 到 126），不含空格
• 每个 add 操作的 ID 唯一
• delete 的 ID 保证合法
• 每个 ID $i$ 满足 $0 \le i \le n$

---

输出格式

程序应输出 $n$ 行。对于每个操作，输出一个整数 $i$，表示该操作后建议的自动补全模式 ID。如果没有匹配，输出 $-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