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.