Hey, do you want to hear something amazing? llHoerlWdo
Tanaka is a crazy idiot. When she finds a string S, she puts it into a M∗N matrix from top-left to bottom-right, and then swaps two columns for T times.
The method to put S in to a M∗N matrix is like this:
S[0] S[1] ... S[N-1]
S[N] S[N+1] ... S[2*N-1]
... ... ... ...
... ... ... ...
S[N*(M-1)] ... S[N*M-1]
For example,if Tanaka finds a string “HelloWorld”, and puts it into a 2∗5 matrix.
the matrix is:
H e l l o
W o r l d
and then swaps 3 times (1, 3), (2, 5), (2, 4)
Step 1. swap column 1 with column 3
l e H l o
r o W l d
Step 2. swap column 2 with column 5
l o H l e
l d W l o
Step 3. swap column 2 with column 4
l l H o e r l W d o
Now, you receive the matrix which has been swaped T times from Tanaka.
Can you recover the original string from the swaped array.
If you can, Tanaka may be happy to make friends with you.
There’re three numbers M, N, T on the first line.
The following M lines contains N characters on each line, denoting the matrix after T swaps.
Each characters are separated by whitespace.
And the next T lines consisting of two numbers Ai Bi on each line.
Ai Bi means Tanaka swaped column Ai with column Bi on the i-th swap.
Print the original string S.
Remember ‘\n’ on the end of line.