Mămăligă 是一种由粗磨玉米粉煮制而成的副食。通常，它被用作 Tochitură（炖肉）、Sarmale（菜卷）、Pastramă（熏肉）等菜肴的配菜。

Costel 和 Tanaka 是 PESI 家族中最调皮的孩子，他们通常在应该解决 CP（算法竞赛）问题的时候，却为了最新计算机科学论文的长篇讨论而争吵。因为他们是两个调皮的男孩，PESI 的父母给他们布置了一项任务：在 Mămăligă 烹饪时搅拌大锅里的混合物。当然，了解他们过去的表现就会知道，他们不可能不为 Mămăligă 的配方而争吵。

大锅可以表示为一个 $n \times n$ 的矩阵 $a$，其中每个单元格包含一个十进制数字，表示大锅该部分 Mămăligă 块的大小。因为大锅很大，男孩们必须用一把大勺子来搅拌，每个人都用双手握着它。

在任何时刻，勺子都位于矩阵中的某个单元格 $(i, j)$，其中 $i, j \in \{1, 2, \dots, n\}$。我们还记录 Mămăligă 的得分 $r$。最初，勺子位于单元格 $(i_0, j_0)$，且 $r = a_{i_0 j_0}$。

Mămăligă 需要 $k$ 秒来烹饪。在第 $t$ 秒（$1 \le t \le k$）：

• 控制勺子的男孩是 $w_t$：如果 $w_t = \text{"T"}$ 则为 Tanaka，如果 $w_t = \text{"C"}$ 则为 Costel。
• 该男孩将勺子从当前单元格 $(i, j)$ 移动到某个单元格 $(i', j')$。
• 对于每个坐标，移动勺子的最大距离为 $p_t$。形式化地， $|i - i'| \le p_t$ 且 $|j - j'| \le p_t$。
• 注意，勺子可以移动到同一个单元格，这仍然被视为一次移动。
• 一旦勺子移动，得分 $r$ 变为 $10 \cdot r + a_{i' j'}$。

$k$ 秒后，$r$ 的值即为最终得分。注意，这个值最多有 $k + 1$ 位数字。Tanaka 认为最终得分越小，他们做得越好；但 Costel 想法相反，希望让最终得分尽可能大。

给你数组 $p_1, \dots, p_k$ 和字符串 $w_1 \dots w_k$。对于每个起点 $(i_0, j_0)$（其中 $i_0, j_0 \in \{1, \dots, n\}$），假设男孩们根据各自的目标做出最优选择，求出 $r$ 的最终值，并输出 $r \bmod 666\,013$。

输入格式

输入的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 240$，$2 \le k \le 700$）。

第二行包含 $k$ 个整数 $p_1, p_2, \dots, p_k$，用空格隔开（$1 \le p_i \le n$）。

第三行包含一个长度为 $k$ 的字符串 $w$，不含空格（$w_i \in \{\text{T}, \text{C}\}$）。

接下来是矩阵 $a$。它由 $n$ 行组成。每行包含一个长度为 $n$ 的十进制数字字符串，不含空格。

输出格式

输出 $n$ 行，每行包含 $n$ 个值。第 $i$ 行的第 $j$ 个值应为当 $i_0 = i$ 且 $j_0 = j$ 时 $r \bmod 666\,013$ 的值。

样例

输入样例 1

3 4
1 2 1 1
TCCT
321
112
011

输出样例 1

31331 21331 11331
10331 10331 21331
331 10331 11331

输入样例 2

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

输出样例 2

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