Description

 

Megumin, a talent explosion magic archwizard, spends a lot of time studying explosion magic spells. For two magic spells A and B, she found that she can combine them together to create a powerful magic spell. Moreover, if the last k characters of A matches the first k characters of B, they can be merged to obtain a more powerful spell. Megumin finds out that the shortest combination of the two spells has maximum power.

For example, if A = "xxxababa" and B = "babayyy", there are severals ways to combine them together:

1. "xxxababababayyy", by simply concatenating A and B, sharing no common characters.

2. "xxxabababayyy", by sharing "ba", the last 2 characters of A and the first 2 characters of B.

3. "xxxababayyy", by sharing "baba", the last 4 characters of A and the first 4 characters of B.

Among all ways of combination, "xxxababayyy" has the maximum power.

Given two magic spells A and B, please output the combination of A and B with maximum power.

Implementation Hints

1. Use strlen() to retrieve length of a string. Remember to #include <string.h>

2. Be careful when using strlen(), or your program might run slowly.

Input

The first line is an integer T, meaning that the input has T test data. Each test data contains a single line.

In each test data, there are two magic spells A and B. Is is guaranteed that A and B only contains lower case alphabets (a-z).

Input consists of two lines. The first line contains A and the second line contains B. It is guaranteed that A and B only contains lower case alphabets (a-z).

• 1 <= T <= 10

• 1 <= |A|, |B| <= 1000

Output

For each test data, please output the answer in one line.  Remember to add new line character ('\n') in the end of each test data.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Story

(The following story is irrelevant to the problem description.)

Thanks to your help with Red Cape Flying Cat's homework, he successfully got his assignment grade for this week!

The good news is that Red Cape Flying Cat figured out another way to earn his credits: taking "Competitive Programming (I)" through "Competitive Programming (XLII)" simultaneously! This way, he will earn 126 credits and never be short of credits again!

However, to pass "Competitive Programming (XVII)", he must complete the class assignments. Just like last time, he is asking you, who can finish this assignment quickly during the "Introduction to Programming (II)" Lab, to do it for him.

Problem Statement

Red Cape Flying Cat has an r x c matrix consisting only of characters . and lowercase English letters.

Red Cape Flying Cat wants to perform q operations on this matrix in the given order. There are four types of operations:

• 1: Transpose the entire matrix across the main diagonal.

• 2: Transpose the entire matrix across the anti-diagonal (secondary diagonal).

• 3 idx dir k: In the idx-th row of the matrix, push the k letters closest to the dir direction towards the dir direction (dir = 0 is right, dir = 1 is left).

• 4 idx dir k: In the idx-th column of the matrix, push the k letters closest to the dir direction towards the dir direction (dir = 0 is up, dir = 1 is down).

Definition of the "Push" operation for types 3 and 4: Given the push direction dir, we select the k lowercase English letters in the specified row or column that are closest to the dir boundary. If the total number of lowercase letters in that row or column is less than or equal to k, all letters are selected.

Next, these selected letters are pushed as far as possible towards the dir direction until they hit the matrix boundary or another selected letter, packing tightly together. Since the selected letters are already the ones closest to the dir boundary, they will never be blocked by unselected letters. The unselected letters remain in their original positions. Any empty spaces left behind by the moved letters are filled with ..

Note that after a type 1 or 2 operation, the number of rows and columns may change. All subsequent operations are based on the new dimensions.

After all operations are completed, please output the final state of the matrix.

Sample Explanation

The following provides an explanation for the first test case in the sample input.

The following provides an explanation for the second test case in the sample input.

Subtasks

The constraints for the test cases of this problem are as follows:

Constraints		Test Cases
q = 0		1
Only operation 1		2
Only operation 2		3
Only operation 3		4-5
Only operation 4		6-7
Guaranteed r = c		8
No additional constraints		9-10

Note: It is strongly recommended that you implement each operation step by step and pass test cases 2 through 7 before attempting to solve the entire problem.

Input

The first line of the input contains a single integer t (1 <= t <= 20) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers r and c (1 <= r, c <= 50) — the initial number of rows and columns of the matrix.

The following r lines each contain a string of c characters. The j-th character of the i-th string represents the element at the i-th row and j-th column of the matrix. Each character is either . or a lowercase English letter.

The next line contains a single integer q (0 <= q <= 50) — the number of operations.

The following q lines describe the operations. Each line starts with an integer representing the type of operation (1, 2, 3, or 4).

• If the type is 1 or 2, there are no additional integers.

• If the type is 3, it is followed by three integers idx, dir, and k (1 <= idx <= r', 0 <= dir <= 1, 0 <= k <= 10^9), where r' is the current number of rows.

• If the type is 4, it is followed by three integers idx, dir, and k (1 <= idx <= c', 0 <= dir <= 1, 0 <= k <= 10^9), where c' is the current number of columns.

It is guaranteed that the row or column corresponding to idx always exists at the exact moment the operation is performed.

Output

For each test case, output the final state of the matrix after all operations are completed. Let r' and c' be the final number of rows and columns. Output r' lines, each containing a string of c' characters representing the matrix.

Don't forget to add a line break at the end.

Sample Input  Download

Sample Output  Download

Tags

Discuss