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
| Input | Output |
|---|---|
4 3 hello world abcde xyz 1 happy 2 cold 1 word | ello abcde xyz |
| Input | Output |
|---|---|
1 2 abcdefghijklmnopqrstuvwxyz 1 abcdefg 2 jklmnopqrstuvwxyz | hi |
