Problem Description

There are $n$ pairwise distinct command strings $t_i$ ($1 \leq i \leq n$), each consisting only of lowercase letters. You need to implement a command line that supports command auto-completion.

Your input area is a string $s$. It can accept lowercase letters $\text{'a'-'z'}$, the $\text{Tab}$ key (denoted by $\text{'T'}$), the $\text{Enter}$ key (denoted by $\text{'E'}$), and the $\text{Backspace}$ key (denoted by $\text{'B'}$). The rules are as follows:

1. When you receive a lowercase letter $c$, append $c$ to the end of the input area string $s$.

2. When you receive the $\text{Backspace}$ key, it will try to delete the last character:

   • If the input area string $s$ is empty, do nothing.
   • If the input area string $s$ is not empty, discard the last character of $s$.

3. When you receive the $\text{Tab}$ key, perform one smart completion on $s$. The completion rules are:

   • Let the set of command strings with prefix $s$ be $T$.
   • If $T$ is empty, do nothing.
   • If $T$ is not empty, set $s$ to $\text{lcp}(T)$. Here $\text{lcp}$ means the longest common prefix, i.e., the longest string that is a prefix of every string in $T$.

4. When you receive the $\text{Enter}$ key, it will try to execute the command $s$:

   • If there exists a command string $t_i = s$, output the command index $i$.
   • If there is no command string $t_i = s$, output $-1$.
   • Whether the execution succeeds or not, clear the input area $s$.

Given the input string $p$ that you receive, you need to output the result of each $\text{Enter}$ key execution.

Input Format

The first line contains two integers $n$ and $m$ ($1 \leq n \leq 10^5, 1 \leq m \leq 5 \times 10^6$), the number of command strings and the length of the input string, separated by spaces.

The next $n$ lines each contain a string $t_i$ consisting only of lowercase letters, representing a command string. It is guaranteed that $\sum_{i=1}^{n} |t_i| \leq 10^6$ and all command strings are pairwise distinct.

The last line contains a string $p$ ($|p|=m$), representing the input string. It is guaranteed that $p$ consists only of $\text{\{'a'-'z', 'T', 'B', 'E'\}}$.

Output Format

Given the input string $p$ that you receive, you need to output the result of each $\text{Enter}$ key execution.

7 40
kill
killall
rm
rmdir
ifconfig
ifdown
ll
kTBlEkTaTEiTcBdTElTExjtuTExjtuBBBBBrTdTE

1 2 6 7 -1 4 

Hint

Initially, the input area string $s=""$.

After inputting $\text{'k'}$, the input area string becomes $s="k"$.

After inputting $\text{'T'}$, perform smart completion. At this time, $T=\{"kill","killall"\}$, and $\text{lcp}(T)="kill"$. Therefore, the input area string becomes $s="kill"$.

After inputting $\text{'B'}$, the input area string becomes $s="kil"$.

After inputting $\text{'l'}$, the input area string becomes $s="kill"$.

After inputting $\text{'E'}$, since $t_1=s$, you should output $1$.

Translated by ChatGPT 5