P14014 [ICPC 2024 Nanjing R] 嘿，有看到我的袋鼠吗？

$\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 题《啊，昨日重现》要求选手构造一张输入地图，以证明以下代码并不是上述问题的解： ```cpp #include using namespace std; string s = "UDLR"; int main() { srand(time(NULL)); for (int i = 1; i 1$ 且 $(i-1,j)$ 不是墙，它会移动到 $(i-1,j)$，否则它会待在原地。 - 按键 D：若 $i1$ 且 $(i,j-1)$ 不是墙，它会移动到 $(i,j-1)$，否则它会待在原地。 - 按键 R：若 $j 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}$。