Description

There are N students in the class, and now they're going to play the game of making sentences again.
Similarly, there are rules for making sentences: the teacher will randomly select students who can make sentences, and randomly decide what they can do.

There are 4 types of operations (the students are indexed from 1 to N):

1. reverse x: reverse student x's sentence
2. print x: print student x's sentence, and a newline character at the end of the line
3. append x y: append student x's sentence to student y's sentence, if y.length < x.length, otherwise append y's sentence to x's sentence ("y.length" means length of student y's sentence; "x.length" means length of student x's sentence)
4. delete s x: delete the first occurrence of s in student x's sentence (do nothing if the sentence does not contain s)

Note: Please use malloc() and free() properly.

Input

The first line contains two integers N, M: the number of students and the number of operations.
Then the following N lines, each line contains a string, where the i + 1 th line represents the initial value of the i th student's sentence.
The last M lines, each line contains one type of operation.

Constraints:
0 < x, y <= N <= 100
0 < M <= 1000
|s| <= 10000

The sentences would only contain lowercase letters.
Note that the length of a student's sentence may exceed 10000 after some operations.

Testcases 1~2: operations can only be "reverse" or "print"
Testcases 3~4: operations can only be "reverse", "print" or "append"
Testcases 5~6: no further constraints

Output

Output student x's sentence when performing the operations of "print".

Sample Input  Download

Sample Output  Download

Tags

Discuss