Garbling Game

Pavel invented a game played on a matrix of integers. He starts with an $r \times c$ matrix ($r$ rows, $c$ columns) filled with the numbers $1$ through $rc$ from left to right and top to bottom: $1$ sits in the upper-left corner and $rc$ in the lower-right corner. Thus the cell in row $i$ and column $j$ (both $1$-indexed) initially holds the value $(i-1)\cdot c + j$.

He then repeatedly rearranges the matrix and writes a sequence of numbers on a separate sheet; he calls this the garbling of the matrix. The rearrangement is driven by a garbling map: an $(r-1) \times (c-1)$ matrix whose entries are the letters L, R, and N.

Pavel plays in a series of turns. The turns visit, in row-major order, every cell that can be the upper-left corner of a $2 \times 2$ block — that is, every cell except those in the last row or the last column: $(1,1), (1,2), \dots, (1,c-1), (2,1), \dots, (r-1,c-1)$. After the $(r-1)(c-1)$-th turn he returns to cell $(1,1)$ and continues in the same order, so the visited cells repeat with period $(r-1)(c-1)$.

On each turn Pavel first writes down the number currently stored in the visited cell. He then reads the letter of the garbling map at that same position and rearranges the $2 \times 2$ block whose upper-left corner is the visited cell:

• R — the block is rotated one quarter-turn clockwise.
• L — the block is rotated one quarter-turn counterclockwise.
• N — the block is left unchanged.

For a block

a b
c d

a clockwise rotation makes it

c a
d b

and a counterclockwise rotation makes it

b d
a c

As an illustration, with the $4 \times 5$ initial matrix and the garbling map

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

the first six numbers Pavel writes are $1, 7, 7, 9, 1, 8$ (on the fifth turn the visited cell holds $1$ and the map letter is N, so nothing moves).

Given the garbling map and the number of turns $n$ Pavel makes, determine how many times each number is written down. Because the counts can be large, output each of them modulo $10^5$.

The first line contains three integers $r$, $c$, and $n$, where $r$ and $c$ ($2 \le r, c \le 300$) are the dimensions of the initial matrix and $n$ ($0 \le n < 10^{100}$) is the number of turns Pavel makes.

Each of the next $r - 1$ lines contains $c - 1$ characters, each R, L, or N, giving one row of the garbling map.

Print $rc$ lines. On the $i$-th line print the number of times the value $i$ is written down during Pavel's $n$ turns, taken modulo $10^5$.