King Brian has recently gotten interested in manipulating strings. Today, he decided to study the Suffix Automata (SAM) data structure. However, he found it too complicated, and decided to pose this simpler problem instead:
Given an array of strings , initially filled with a single string , maintain two types of operations:
C x_i c_i: Copy the string at and append the character to it. Then, append that new string to the back of .
Q s_i: Given a query string , output the index of the string in that shares the longest common prefix with . If multiple strings suffice this requirement, the one with the smallest index will be the answer. Additionally, if there is no valid index,
-1is the answer.
Indices are 1-indexed.
Of course, being a king, he isn't content with answering a few measly queries. Instead, he wants you to answer of them! Are you up to the challenge?
Note: for a string denotes the length of .
For all subtasks:
, all , and all will be made of lowercase English letters.
The sum of all will be .
For 3 of 15 available marks, and the sum of all will be .
The first line of input contains and .
The next lines of input contain a query of one of the types specified above.
For each query, output the answer on a new line.
chad 12 C 1 l C 1 l C 3 i C 4 a C 2 e C 6 x C 5 m Q cha Q z Q chadl Q chadlliam Q chadliam
1 -1 2 2 8
After all the updates, the array of strings looks like this:
[chad, chadl, chadl, chadli, chadlia, chadle, chadlex, chadliam]