# 50095. Lines of Words

## I'm a slow walker, but I never walk backwards.

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.

 applebird catdog elephant frog

Now we will process requests for switching words. A request $(l_{1}, w_{1}, l_{2}, w_{2})$ indicates that we need to switch words $(l_{1}, w_{1})$ and $(l_{2}, w_{2})$. 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.

 frogbird catdog elephant apple

$N$ is the number of lines, $L_{i}$ is the number of words in the $i_{th}$ line, $L$ is the total number of 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 \lt 32$
• $L_{i} \lt 32$
• $L \lt 1024$
• $w \lt 32$
• $W \lt 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 \lt 32$
• $L_{i} \lt 32$
• $L \lt 1024$
• $w \lt 1024$
• $W \lt 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. That is, whenever you read a word you advance the pointer to the next available position in that array. This can also save storage.
• $N \lt 1024$
• $L_{i} \lt 1024$
• $L \lt 16384$
• $w \lt 1024$
• $W \lt 10000000$

## 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 $L_{i}$ 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 $l_{1}$, $w_{1}$, $l_{2}$, $w_{2}$.

## 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

 3applebird catdog elephant frog10 0 1 0

## Sample Output 1

 birdapple catdog elephant frog

## Sample Input 2

 3applebird catdog elephant frog50 0 1 01 0 1 11 1 2 02 0 2 12 1 2 2

## Sample Output 2

 birdcat dogelephant frog apple