Cifre

Tanaka și Costel construiesc împreună un număr întreg $r$ de cel mult $K + 1$ cifre, conform următoarei reguli. Ei au în fața lor pe ecranul unui calculator o matrice $A$ % sau $A = (a_{ij})$
cu $N$ linii și $N$ coloane, unde $A_{ij} \in \{0, \ldots, 9\}$. Mai au și două șiruri $P_1, \ldots, P_{K}$ de numere întregi și $J_1, \ldots, J_{K}$ de caractere din mulțimea $\{T, C\}$. Cursorul calculatorului este pus mereu pe o căsuța $(i, j)$ din matrice cu $i, j \in \{1, \ldots, N\}$, inițial la coordonata $(i_0, j_0)$. Numărul $r$ este inițial $A_{i_0 j_0}$. Cei doi mută cursorul. Dacă cursorul este la poziția $(i, j)$, și cursorul se mișcă a $t$-a oară, atunci jucătorul $J_t$ (Tanaka dacă $J_t = T$, Costel dacă $J_t = C$) poate să îl mute la poziția $(i', j')$ dacă $i', j' \in \{1, \ldots, N\}$, $|i - i'| \leq P_{t}$ și $|j - j'| \leq P_{t}$. Odată mutat cursorul la poziția $(i', j')$, numărul $r$ este înlocuit cu $10 \cdot r + A_{i'j'}$. Cei doi mută cursorul de $K$ ori în total.

Cerință

Cum Tanaka este pesimist, el vrea să facă numărul $r$ cât mai mic, iar Costel vrea să îl facă cât mai mare. Dându-se $N, K$, șirul $P_t$ și șirul $J_t$, și matricea $A$, să se calculeze numărul $r$ obținut pentru fiecare poziție de start $(i_0, j_0)$ cu $i_0 \in \{1, \ldots, N\}, j \in \{1, \ldots, N\}$.

Date de intrare

Fișierul de intrare cifre.in conține pe prima linie numerele naturale $N$ și $K$. Pe a doua linie conține șirul $P_t$. Pe a treilea linie conține șirul $J_t$. Urmează reprezentarea matricii $A$.

Date de ieșire

Fișierul de ieșire cifre.out trebuie să conțină răspunsurile cerute, reprezentate ca matricea $R$ cu $N$ linii și $N$ coloane, unde $R_{ij}$ este valoarea lui $r$ pentru $i_0 = i, j_0 = j$. Fiecare număr se va afișa modulo $666 \ 013$.

Restricții și precizări

• $1 \leq N \leq 240$
• $1 \leq K \leq 700$
• $J_i \in \{T, C\}$
• $1 \leq P_i \leq N$
• Tanaka va muta cursorul în așa fel încât numărul $r$ final să fie cât mai mic, iar Costel va muta cursorul în așa fel încât numărul $r$ final să fie cât mai mare.

Exemplul 1

cifre.in

3 4
1 2 1 1
TCCT
321
112
011

cifre.out

31331 21331 11331
10331 10331 21331
331 10331 11331

Exemplul 2

cifre.in

5 6
1 2 3 1 2 2
TCTCTT
12345
54310
12314
34622
23411

cifre.out

485487 153461 496448 64422 398409
489409 155422 496448 394487 60500
494487 162461 496448 394487 64422
496448 164422 166383 162461 162461
262461 596448 164422 494487 494487