Description

ACM-ICPC judges, sometimes, play computer games, such as Alphariz. In the game of Alphariz, you are given a table (e.g., Table I) of alphabetic characters. At each step of the game, you choose a table entry E containing a non-blank character ch. Then, you recursively identify all the friends of E. The friends are the existing table entries containing the same character ch which are located immediately to the left, right, up, and down directions of E, and their friends in turn, until no new friends can be located. Then, you replace the characters in E and its found friends with blanks. Table II shows the result of applying the latter rule on Table I, starting at entry E in row 1 and column 2, where ch is 'a'.

Then, while still in the same step, you shift all the non-blank characters to the left and the blanks to the right, as is shown in Table III. Next, you shift all non-blank characters down and the blanks are shifted up as is shown in Table IV. Note that possible full blank rows or columns are to be deleted.

You are to write a program that given the initial table and a sequence of selected table entries, apply the above rules for each given table entry, one after another, and report the final resulting table.

Input

The input consists of several test cases. Each test case starts with the character map which is given in m lines of length n characters (1 <= m, n <= 1000). Characters in the initial map are all lowercase letters. After this, there is a single line containing a single integer k which is the number of selected table entries, followed by k lines, containing two integers r (1 <= r <= m) and c (1 <= c <= n) which are the row and the column numbers of the table entry, respectively. Besides, the items are always inside the current table.

Output

The output for the ith test case should start with a line in the following format:

Test case #i: After the first line, the final map should be written with the same format as in the input.

aabbb
abaab
aaaba
abbaa
1
1 2
aba
bbc
2
1 3
2 2

Test case #1:
bb
bb
bab
bbaa
Test case #2:
a
c

Source

Tehran 2005