Garbled Game (from NEERC 2009)

Pavel had invented a new game with a matrix of integer numbers. He takes an 
r x c matrix with r rows and c columns that is filled with numbers from 1 
to rc left to right and top to bottom (1 is written in the upper-left 
corner, rc is written in the lower-right corner).  Then he starts to 
rearrange the numbers in the matrix by following the rules that are 
explained below and writes down a sequence of numbers on a separate piece 
of paper.  He calls it garbling the matrix.

The rules of rearrangement are defined by a garbling map that is an
(r-1) x (c-1) matrix of letters L, R, and N.  An initial 4 x 5 matrix 
and a sample 3 x 4 garbling map for it are shown below.

1  2  3  4  5
6  7  8  9  10
11 12 13 14 15
16 17 18 19 20

L R L R
N L L R
L N N L

Pavel garbles the matrix in a series of turns.  On his first turn Pavel 
takes the number in the first row and the first column (1 in the example
above) and writes it down.  Having written down the number he performs 
one garbling turn:  Pavel looks at the letter in the garbling map that 
corresponds to the position of the number he has just written down (on 
the first turn it is the letter in the upper-left corner).  Depending on 
the letter in the garbling map, the 2 x 2 block of the matrix whose 
upper-left corner contains the number he has just written is rearranged 
in the following way:
R : the block is rotated clockwise.
L : the block is rotated counterclockwise.
N : Pavel does not change the matrix on this turn.

On the second turn Pavel takes the number in the first row and second 
column, writes it down, and performs the garbling turn, and so on. 
After c-1 turns he finishes the first row and moves to the second
row and he proceeds in this way left to right and top to bottom. 
In (r-1)(c-1) turns he has written down (r-1)(c-1) numbers and garbled 
the whole matrix, so he starts again in the upper-left corner continuing
garbling the matrix from left to right and top to bottom.

The matrices below show the effect of the first four turns with the 
sample garbling map.

In the first turn, Pavel writes down "1" and does an L rotation, yielding:

2  7  3  4  5
1  6  8  9  10
11 12 13 14 15
16 17 18 19 20

Then Pavel writes "7" and does an R rotation:

2  6  7  4  5
1  8  3  9  10
11 12 13 14 15
16 17 18 19 20

Then Pavel writes another "7" and does an L rotation:

2  6  4  9  5
1  8  7  3  10
11 12 13 14 15
16 17 18 19 20

Then Pavel writes "9" and does an R rotation:

2  6  4  3  9
1  8  7  10 5
11 12 13 14 15
16 17 18 19 20

Then Pavel writes a "1" and does nothing to the matrix.

Then Pavel writes an "8" and does an L rotation:

2  6  4  3  9
1  7  13 10 5
11 8  12 14 15
16 17 18 19 20

The following sequence of numbers is written down in the first 6 turns: 
1 7 7 9 1 8.  

Given the garbling map and the number of moves Pavel makes in this game, 
find out how many times each number gets written down by Pavel. You need 
to provide the answer modulo 10^5.

Input

The input will consist of several instances.

The first line of each input instance contains three integer numbers r, c, and 
n, where r, c (2 <= r, c <= 300) are the dimensions of the initial matrix, 
n (0 <= n <= 10^100) is the number of turns Pavel makes.
The following r-1 lines contain a garbling map with c-1 characters R, L, 
or N on each line.

The end of the input will be indicated by a line with r=c=n=0.

Output

For each input instance, output rc lines with one integer per line.  On the 
ith line write the number of times number i gets written down by Pavel (modulo
10^5).  Output a blank line between instances (but do not output a blank
line at the beginning or end of the output).

Sample Input

4 5 6
LRLR
NLLR
LNNL
4 5 666666
LRLR
NLLR
LNNL
0 0 0

Sample Output

2
0
0
0
0
0
2
1
1
0
0
0
0
0
0
0
0
0
0
0

37038
37038
0
0
30864
37036
11112
30864
30864
30864
30864
30864
11110
30865
18519
30864
30864
0
18518
18518