Execute Queries on Strings

Given an initial list of strings and a series of queries, your task is to process the queries and update the strings accordingly.

There are two types of queries:

• P X Y: Append string Y to the end of the X^th string.
• L A B: Find the first occurrence (1-indexed) of the A^th string in the B^th string. Print the starting position if found, or -1 if not found.

Note that all indices are 1-indexed.

inputFormat

The first line contains two integers n and q, representing the number of initial strings and the number of queries, respectively.

The next n lines each contain a non-empty string, representing the list of initial strings.

Each of the next q lines represents a query in one of the following two formats:

• "P X Y": Append the string Y to the X^th string.
• "L A B": Output the starting position (1-indexed) of the first occurrence of the A^th string in the B^th string. If it does not occur, output -1.

outputFormat

For each query of type "L", output the result on a separate line.## sample

3 5
hello
world
example
P 1 everyone
L 1 2
L 2 3
P 3 code
L 3 1

-1
-1
-1