P14153 [ICPC 2022 Nanjing R] 停停，昨日请不要再重现
题目描述
继 2018，2019，2020 和 2021 年成功承办赛事之后，南京航空航天大学（NUAA）将连续第五年承办国际大学生程序设计竞赛（ICPC）。
在 2018 与 2019 年，“中二之力”队与“三个顶俩”队为清华大学赢得了冠军。在 2020 与 2021 年，北京大学的“逆十字”队连续赢得冠军。该队也在达卡举办的第 45 届国际大学生程序设计竞赛全球总决赛中获得了亚军，创造了东大陆区域过去六年来的最佳成绩。让我们恭喜他们，同时也非常期待他们在 2022 年南京站的表现！
今年，将会有约 $500$ 支队伍参与南京站的竞赛。本次竞赛将会颁发至多 $35$ 项金奖，$70$ 项银奖与 $105$ 项铜奖。让我们期待选手们出色的表现！
虽然由于疫情，我们（又一次）无法在南京相聚，我们仍然需要感谢竞赛组委会与志愿者们的努力付出。感谢你们为本次竞赛做出的贡献！
:::align{center}
:::
在 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 本题中，网格中的每个格子都有恰好一只袋鼠。您需要构造一个仅由字符 `U`，`D`，`L` 和 `R` 组成的操作序列。在应用该操作序列后，所有袋鼠必须聚集在指定格子 $(a,b)$ 中。操作序列的长度不能超过 $3(n-1)$。同往常一样，所有袋鼠会根据您的命令同时移动。
在 2022 年的竞赛中，袋鼠题又回来啦！我们不知道为什么命题组的成员们那么喜欢袋鼠，但题目如下：
给定一张 $n$ 行 $m$ 列的网格，在位于第 $i_h$ 行第 $j_h$ 列的格子上有一个洞，其它每个格子都是空地并且都有一只袋鼠。
相似地，袋鼠可以被键盘上的 U，D，L，R 键控制。所有袋鼠会同时根据按下的按键移动。具体来说，对于一只位于第 $i$ 行第 $j$ 列的格子（用 $(i,j)$ 表示）上的袋鼠：
- 按键 U：它会移动到 $(i-1,j)$。
- 按键 D：它会移动到 $(i+1,j)$。
- 按键 L：它会移动到 $(i,j-1)$。
- 按键 R：它会移动到 $(i,j+1)$。
如果一只袋鼠踩到了洞（也就是说，$i = i_h$ 且 $j = j_h$）或者移动到了网格外面，它将被从网格上移除。
问题在于，$i_h$ 与 $j_h$ 的值是未知的。您只知道一个仅由字符 `U`，`D`，`L`，`R` 组成的操作序列，以及一个整数 $k$ 表示应用这个操作序列之后，网格上恰有 $k$ 只袋鼠存留。
请计算有多少位置可能存在洞。也就是说，计算满足以下条件的整数对 $(i_h, j_h)$ 的数量：
- $1 \le i_h \le n$，$1 \le j_h \le m$。
- 洞位于 $(i_h, j_h)$。
- 应用给定的操作序列后，网格上恰有 $k$ 只袋鼠存留。
输入格式
有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数，对于每组测试数据：
第一行输入三个整数 $n$，$m$ 与 $k$（$1 \le n, m \le 10^3$，$0 \le k < n \times m$）表示网格的大小以及应用操作序列后网格上存留的袋鼠数量。
第二行输入一个字符串 $s_1s_2\cdots s_l$（$s_i \in \{\text{`U'}, \text{`D'}, \text{`L'}, \text{`R'}\}$，$1 \le l \le 10^6$）表示操作序列。
保证所有数据 $n \times m$ 之和以及操作序列长度之和均不超过 $10^6$。
输出格式
每组数据输出一行一个整数表示有多少位置可能存在洞。
说明/提示
对于第一组样例数据，有 $2$ 个位置可能存在洞。
第一个可能的位置是 $(3, 4)$。
:::align{center}
:::
第二个可能的位置是 $(4, 3)$。
:::align{center}
:::