String Game

You have a list of N strings, denoted by A1, A2, ..., AN. Each string consists of lowercase English letters.

You are asked to perform M operations on that list. Each operation is one of the following types:
Type 1: A string S will be given. For each element Ai, you will remove the longest common prefix of Ai and S from the left side of Ai.

Type 2: A string S will be given. For each element Ai, you will remove the longest common suffix of Ai and S from the right side of Ai.

After performing all the operations, you have to print the list.

Input

Input begins with two integers N and M representing the number of strings in the list and the number of operations.
The next N lines contain the list elements A1, A2, ..., AN.

Each of the next M lines contains the operation type T and a string S.

Constraints

• 0 < N ≤ 1000000
• 0 ≤ M ≤ 1000000
• T is either 1 or 2
• All the input strings are non-empty and contain only lowercase English letters. Sum of the lengths of the input strings will not exceed 2000000.

Output

Print the final list after performing all the operations.

Samples

4 3
hello
world
abcde
xyz
1 happy
2 cold
1 word

ello

abcde
xyz

1 2
abcdefghijklmnopqrstuvwxyz
1 abcdefg
2 jklmnopqrstuvwxyz

hi