Ancient Plates

Some decades ago, archaeologists discovered plates covered with text in an ancient temple. The individual symbols were already known, but how the text as a whole had been encrypted remained a mystery for a long time. Last year, however, a second temple was discovered in the same area. Its interior closely resembled the first, so it is believed to have been built at the same time. This second temple also contained plates, but their contents looked quite different. After a year of research, the archaeologists proposed the theory that these plates hold the rules (the code) needed to decipher the text found in the first temple.

Your task is to write a program that automates deciphering the text on the plates by applying the rules proposed by the archaeologists.

There are two kinds of rules: PERM and SHIFT. Both apply to one of three targets: lines of the text (L), words (W), or characters (C).

A PERM rule consists of the string PERM, a single blank, the letter denoting the target, and one or more index pairs separated by blanks. Each index pair i,j is two positive integers $i$ and $j$ joined by a single comma.

Depending on the target, for each pair $i, j$ — processed from left to right — the PERM rule does the following:

• L: exchange line $i$ and line $j$.
• W: exchange word $i$ and word $j$ in every line.
• C: exchange character $i$ and character $j$ in every word of every line.

If at least one of the objects to be exchanged does not exist, that exchange is skipped. For example, PERM W 2,7 asks to exchange the 2nd and 7th word in every line, but some line may have only five words; in that line nothing is done, while the exchange is still performed in every other line that has at least seven words.

A SHIFT rule consists of SHIFT, a single blank, the target letter, a single blank, and an integer $k$. The rule shifts the target $|k|$ times: to the left (upward for lines) when $k > 0$, and to the right (downward for lines) when $k < 0$. A single shift works as follows:

• L: shifting left (up) moves every line up by one, and the first line becomes the last line; shifting right (down) moves every line down by one, and the last line becomes the first line.
• W: shifting left moves the words of each line one position to the left, and the first word becomes the last word; shifting right does the opposite.
• C: shifting left moves the characters of each word one position to the left, and the first character becomes the last character; shifting right does the opposite.

If $k = 0$, no shift is performed.

The first line contains the number of scenarios, i.e. the number of plates to decipher.

For each plate you are first given, on a single line, the number of text lines $l$ $(0 \le l \le 1000)$ to decipher. The next $l$ lines contain that text, and no line exceeds 1000 characters. After that, one line contains the number of rules $r$ $(0 \le r \le 1000)$ to apply, and the following $r$ lines contain those rules in the format described above.

The words of the text are sequences of arbitrary characters (not just letters!) separated by single blanks. No line of the given text starts or ends with a blank, but a line may be empty altogether.

Begin each scenario's output with a line Scenario #i:, where $i$ is the scenario number starting at 1. Then print the $l$ lines of text after all rules have been applied. Separate two consecutive scenarios with a single blank line.