Given N lines of words, switch words among them. We will use (l, w) to indicate the w-th word in the l-th line. Both line and word numbers are from 0. For the example (0, 0) is “apple” (1, 0) is “bird”, and (2, 2) is “frog” for the following input.
apple
bird cat
dog elephant frog
Now we will process requests for switching words. A request (l1, w1, l2, w2) indicates that we need to switch words (l1, w1) and (l2, w2). Note that we guarantee that the indices are all valid.
For example, if the request is (0, 0, 2, 2), then we switch “apple” with “frog”, and the lines change as follow. After finishing processing requests, output the final result in a line by line manner.
frog
bird cat
dog elephant apple
Subtask
N is the number of lines, Li is the number of words in the i-th line, L is the total number of the words, w is the max length of a word and W is the total number of characters (including ‘\0’) in all words.
30 points: The input data is small.
N < 32
Li < 32
L < 1024
w < 32
W < 50000
40 points: W is significantly large, so using “strcpy” function will cause TLE. Instead you should use a 2D pointer array, and switch the pointers only.
N < 32
Li < 32
L < 1024
w < 1024
W < 500000
30 points: N and the the maximum number of words in a line are extremely large, so allocating a 2D pointer array will cause MLE. You should use “two-level pointer”, as in the task last week, to implement the line and word structure. Also the number of characters in a word could vary dramatically, so you need to put all of them in a one-dimensional array to save storage. The is, whenever you read a word you advance the pointer to the next available position in that array. This can also save storage.
The input contains only one test case. The first line contains one integer N, representing the number of lines. The next N lines contains Li words. After N+1 lines, there is a line contains one integer M, representing the number of requests. The next M lines contains four integers l1, w1, l2, w2.
Output Format
Print the N lines in the table in each line, and each word in one line is separated by a single space. And a ‘newline’ after the last word in each line.
Task Description
Given N lines of words, switch words among them. We will use (l, w) to indicate the w-th word in the l-th line. Both line and word numbers are from 0. For the example (0, 0) is “apple” (1, 0) is “bird”, and (2, 2) is “frog” for the following input.
Now we will process requests for switching words. A request (l1, w1, l2, w2) indicates that we need to switch words (l1, w1) and (l2, w2). Note that we guarantee that the indices are all valid. For example, if the request is (0, 0, 2, 2), then we switch “apple” with “frog”, and the lines change as follow. After finishing processing requests, output the final result in a line by line manner.
Subtask
N is the number of lines, Li is the number of words in the i-th line, L is the total number of the words, w is the max length of a word and W is the total number of characters (including ‘\0’) in all words.
figure
Input Format
The input contains only one test case. The first line contains one integer N, representing the number of lines. The next N lines contains Li words. After N+1 lines, there is a line contains one integer M, representing the number of requests. The next M lines contains four integers l1, w1, l2, w2.
Output Format
Print the N lines in the table in each line, and each word in one line is separated by a single space. And a ‘newline’ after the last word in each line.
Sample Input 1
Sample Output 1
Sample Input 2
Sample Output 2