Command Autocomplete Simulation

You are given \(n\) distinct command strings \(t_i\) (each composed only of lowercase letters) where \(1 \le i \le n\). You need to simulate a command line interface that supports command autocompletion.

The interface maintains an input string \(s\) (initially empty) and processes a sequence of keystrokes provided in a string \(p\). The string \(p\) contains lowercase letters (\('a'-'z'\)) and the following special keys: Tab (represented by the character T), Enter (represented by E), and Backspace (represented by B). The simulation follows these rules:

1. If a lowercase character \(c\) is read, it is appended to the end of \(s\).
2. If a Backspace (B) is read:
   • If \(s\) is empty, do nothing.
   • If \(s\) is non-empty, remove the last character from \(s\).
3. If a Tab (T) is read, perform an autocomplete operation:
   • Let \(T\) be the set of all command strings that have \(s\) as a prefix.
   • If \(T\) is empty, do nothing.
   • If \(T\) is non-empty, set \(s\) to \(\mathrm{lcp}(T)\), the longest common prefix of all strings in \(T\).
4. If an Enter (E) is read, attempt to execute the command in \(s\):
   • If there exists a command \(t_i\) such that \(t_i = s\), output its 1-indexed identifier \(i\).
   • If no such command exists, output \(-1\).
   • In either case, clear \(s\) after processing.

Your task is to output the result for each Enter (E) encountered in the keystroke string \(p\>.

inputFormat

The first line of input contains an integer \(n\), the number of command strings.

The following \(n\) lines each contain a distinct command string \(t_i\) composed only of lowercase letters.

The last line contains a string \(p\) which represents the sequence of keystrokes. The string \(p\) consists of lowercase letters, and the characters T (Tab), E (Enter), and B (Backspace).

outputFormat

For each Enter (E) in the keystroke string \(p\), output a separate line containing an integer. The integer is the 1-indexed identifier of the command if \(s\) exactly matches one of the command strings, or \(-1\) if no such command exists.

sample

3
abc
abd
bcd
abTE

-1