你正在设计一款时尚的新文本编辑器，并希望添加一个精妙的自动补全功能来帮助用户节省时间。它的工作原理如下：如果用户输入 “App”，你的编辑器将神奇地推荐单词 “Application”！更棒的是，用户还可以个性化设置编辑器中用于自动补全的单词。

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

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

在每次操作后，你的编辑器应该推荐一个满足以下条件的自动补全候选串 $i$：

1. 字符串 $p_i$ 拥有等于 $t$ 的前缀。
2. 如果有多个满足条件的 $p_i$，选择最长的一个。
3. 如果仍有多个，选择字典序最小的一个。
4. 如果仍有多个，选择 ID 最小的一个。

为了简化问题，对于每次操作，输出推荐的自动补全模式串的 ID。如果没有匹配的模式串，输出 -1。

例如，假设我们有三个候选串：“alice”、“bob” 和 “charlie”，其 ID 分别为 1、2 和 3。起初，屏幕上没有任何内容（即 $t$ 为空），因此应该推荐 “charlie”（ID 为 3），因为它是最长的。接着，假设用户输入了 “b”。你应该推荐 “bob”（ID 为 2），因为它是唯一以 “b” 开头的串。最后，假设用户输入了 “body”。你应该输出 -1，因为没有匹配的模式串。

输入格式

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

共有四种类型的操作：

1. add i p_i
2. delete i
3. append s
4. backspace c

add 操作后跟一个整数 $i$ 和一个模式串 $p_i$，表示用户想要添加一个 ID 为 $i$ 的模式串。delete 操作后跟一个整数 $i$，表示用户想要从模式串集合中删除 ID 为 $i$ 的模式串 $p_i$。append 操作后跟一个字符串 $s$，表示用户在 $t$ 的末尾追加 $s$。backspace 操作后跟一个整数 $c$，表示用户从 $t$ 的末尾删除 $c$ 个字符。所有参数均由单个空格字符分隔。

输出格式

程序应输出 $n$ 行。对于每次操作，输出一个整数 $i$，表示该操作后推荐的自动补全候选串的 ID。如果没有满足要求的 $p_i$，则输出 -1。

数据范围

• $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 $i$ 是唯一的。
• 保证每次 delete 操作的 ID $i$ 都是有效的。
• 每个 ID $i$ 满足 $0 \le i \le n$。

样例

输入样例 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