题目描述

$\textbf{请注意本题不同寻常的空间限制。}$

继 2018，2019，2020，2021，2022 和 2023 年成功承办赛事之后，南京航空航天大学（NUAA）将连续第七年承办国际大学生程序设计竞赛（ICPC）。

在 2018 与 2019 年，“中二之力”队与“三个顶俩”队为清华大学赢得了冠军。在 2020，2021 与 2022 年，北京大学的“逆十字”队赢得三连冠。在 2023 年，来自北京大学的另一支队伍“重生之我是菜狗”赢得了冠军。他们还赢得了第 46 届 ICPC 世界总决赛的冠军，在 13 年后为 EC 赛区重新赢回了奖杯。

今年，将会有约 $335$ 支队伍参与南京站的竞赛。本次竞赛将会颁发至多 $33$ 项金奖，$66$ 项银奖与 $99$ 项铜奖（数字仅供参考）。让我们期待选手们出色的表现！我们还想要感谢竞赛组委会与志愿者们的努力付出。感谢你们为本次竞赛做出的贡献！

:::align{center}

在 2023 ICPC 国际大学生程序设计竞赛亚洲区域赛（南京站）中拍摄的照片 :::

在 2018 年的竞赛中，K 题《袋鼠谜题》要求选手为以下游戏构造一个操作序列：

谜题由一个 $n$ 行 $m$ 列的网格（$1 \le n, m \le 20$）组成，且有一些（至少 $2$ 只）袋鼠位于网格中。玩家的目标是控制袋鼠并把它们聚集在同一个格子中。一些格子里有墙，袋鼠无法进入这些有墙的格子，而其它格子是空的。袋鼠可以从一个空格子移动到上，下，左，右相邻的另一个空格子中。
游戏开始时，每个空格子里都有一只袋鼠。玩家可以通过键盘上 U，D，L，R 四个按键控制袋鼠的移动。所有袋鼠会同时根据您按下的按键移动。 选手需要构造一个长度至多为 $5 \times 10^4$ 且由 U，D，L，R 组成的操作序列以达成目标。

在 2020 年的竞赛中，A 题《啊，昨日重现》要求选手构造一张输入地图，以证明以下代码并不是上述问题的解：

#include <bits/stdc++.h>
using namespace std;
string s = "UDLR";
int main()
{
  srand(time(NULL));
  for (int i = 1; i <= 50000; i++) putchar(s[rand() % 4]);
  return 0;
}

此外，在 2021 年的竞赛（A 题，《呀，昨日再次重现》），2022 年的竞赛（A 题，《停停，昨日请不要再重现》）和 2023 年的竞赛（A 题，《酷，昨日四次重现》）中，每年都有一道与袋鼠相关的问题！我们很想向您介绍所有这些问题，但如果我们每年都这样做，在 3024 年的竞赛中将会有一道题拥有长达 500 页的题面。因此，这次我们省略它们。另外，您可能已经在热身赛中见过它们了。

在 2024 年的竞赛中，如大家期待的那样，袋鼠题又回来啦！我们不知道为什么命题组的成员们那么喜欢袋鼠，但题目如下：

给定一张 $n$ 行 $m$ 列的网格。一些格子里有墙，袋鼠无法进入这些有墙的格子，而其它格子是空的，每个空格子中都有一只袋鼠。袋鼠可以从一个空格子移动到上，下，左，右相邻的另一个空格子中。

袋鼠可以被键盘上的 U，D，L，R 键控制。所有袋鼠会同时根据按下的按键移动。具体来说，对于一只位于第 $i$ 行第 $j$ 列的格子（用 $(i,j)$ 表示）上的袋鼠：

• 按键 U：若 $i>1$ 且 $(i-1,j)$ 不是墙，它会移动到 $(i-1,j)$，否则它会待在原地。
• 按键 D：若 $i<n$ 且 $(i+1,j)$ 不是墙，它会移动到 $(i+1,j)$，否则它会待在原地。
• 按键 L：若 $j>1$ 且 $(i,j-1)$ 不是墙，它会移动到 $(i,j-1)$，否则它会待在原地。
• 按键 R：若 $j<m$ 且 $(i,j+1)$ 不是墙，它会移动到 $(i,j+1)$，否则它会待在原地。

给定一个仅由字符 U，D，L，R 组成的操作序列 $s_1 s_2 \ldots s_k$，我们将根据序列进行无限次操作。具体来说，若 $1 \le t \le k$，则第 $t$ 次操作就是 $s_t$；否则若 $t > k$，则第 $t$ 次操作和第 $(t - k)$ 次操作相同。对于每个 $1 \le i \le n \times m$，求最小的整数 $v_i$，使得执行 $v_i$ 次操作后，最多有 $i$ 个格子里含有袋鼠。

输入格式

每个测试文件仅有一组测试数据。

第一行输入三个整数 $n$，$m$ 和 $k$（$1 \le n, m \le 2 \times 10^5$，$1 \le n \times m \le 2 \times 10^5$，$1 \le k \le 200$），表示网格的行数和列数，以及操作序列的长度。

第二行输入一个字符串 $s_1 s_2 \cdots s_k$（$s_i \in \{\text{`U'}, \text{`D'}, \text{`L'}, \text{`R'}\}$），表示操作序列。

对于接下来 $n$ 行，第 $i$ 行输入一个二进制字符串 $a_{i,1}a_{i,2}\cdots a_{i,m}$（$a_{i,j} \in \{\text{`0'}, \text{`1'}\}$）。若 $a_{i,j} = \text{`1'}$ 则格子 $(i, j)$ 是空的；否则若 $a_{i,j} = \text{`0'}$ 则格子 $(i, j)$ 被阻塞，无法进入。保证网格中至少有一个空格子。

输出格式

输出 $n \times m$ 行，其中第 $i$ 行输出一个整数 $v_i$，表示最少需要几次操作，才能使最多有 $i$ 个格子里含有袋鼠。如果不可能做到，则在这一行输出 $\texttt{-1}$。

3 3 6
ULDDRR
010
111
010

-1
4
2
1
0
0
0
0
0

3 3 6
ULDDRR
010
111
011

7
4
2
1
1
0
0
0
0

1 5 1
R
11111

4
3
2
1
0