题目描述

有 $n$ 个两两互不相同的仅由小写字符构成的命令字符串 $t_i$ ($1 \leq i \leq n$)，你需要实现一个支持命令补全的命令行。

你的输入区是一个字符串 $s$，他可以接受小写字母 $\text{'a'-'z'}$ 和 $\text{Tab}$ 键 (以 $\text{'T'}$ 表示)，$\text{Enter}$ 键 (以 $\text{'E'}$ 表示)，$\text{Backspace}$ 键 (以 $\text{'B'}$ 表示)。规则如下所述:

1. 当你接受小写字符 $c$，将把 $c$ 追加到输入区字符串 $s$ 的末尾。

2. 当你接受 $\text{Backspace}$ 键，将尝试删除最后一个字符:

   • 如果输入区字符串 $s$ 为空，则不进行任何操作。
   • 如果输入区字符串 $s$ 非空，则丢弃 $s$ 末尾的字符。

3. 当你接受 $\text{Tab}$ 键，将会对 $s$ 进行一次智能补全，补全规则如下:

   • 设以 $s$ 为前缀的命令字符串集合为 $T$。
   • 如果 $T$ 为空，则不进行任何操作。
   • 如果 $T$ 非空，则把 $s$ 置为 $\text{lcp}(T)$。这里 $\text{lcp}$ 代表最长公共前缀，含义是最长的，是 $T$ 中每一个字符串前缀的字符串。

4. 当你接受 $\text{Enter}$ 键，将会试图执行命令 $s$:

   • 如果存在命令字符串 $t_i = s$，则输出命令编号 $i$。
   • 如果不存在命令字符串 $t_i = s$，则输出 $-1$。
   • 无论是否执行成功，清空输入区 $s$。

给定你接受到的输入串 $p$，你需要输出每个 $\text{Enter}$ 键执行的结果。

输入格式

输入第一行为两个整数 $n$ 和 $m$ ($1 \leq n \leq 10^5, 1 \leq m \leq 5 \times 10^6$)，为命令字符串的个数和输入串的长度，由空格隔开。

接下来 $n$ 行，每行一个仅由小写字符构成的字符串 $t_i$，为命令串。保证有 $\sum_{i=1}^{n} |t_i| \leq 10^6$ 且命令串互不相同。

最后一行为字符串 $p$ ($|p|=m$)，为输入串。保证 $p$ 仅由 $\text{\{'a'-'z', 'T', 'B', 'E'\}}$ 组成。

输出格式

给定你接受到的输入串 $p$，你需要输出每个 $\text{Enter}$ 键执行的结果。

7 40
kill
killall
rm
rmdir
ifconfig
ifdown
ll
kTBlEkTaTEiTcBdTElTExjtuTExjtuBBBBBrTdTE

1 2 6 7 -1 4 

提示

初始时，输入区字符串$s=""$。

输入 $\text{'k'}$ 后，输入区字符串$s="k"$。

输入 $\text{'T'}$ 后，进行智能匹配。此时 $T=\{"kill","killall"\}$，$\text{lcp}(T)="kill"$。故输入区字符串$s="kill"$。

输入 $\text{'B'}$ 后，输入区字符串$s="kil"$。

输入 $\text{'l'}$ 后，输入区字符串$s="kill"$。

输入 $\text{'E'}$ 后，因为 $t_1=s$，所以应该输出 $1$。