Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

String Game

By shahed95 · Limits 3s, 1.0 GB

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

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

abcde
xyz
InputOutput
1 2
abcdefghijklmnopqrstuvwxyz
1 abcdefg
2 jklmnopqrstuvwxyz
hi

Discussion

Statistics


67% Solution Ratio

JobaidulEarliest, Dec '19

shefinFastest, 0.1s

rifatrraazzLightest, 51 MB

rifatrraazzShortest, 1114B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.