题目描述

Alex 是贪吃蛇游戏的超级粉丝。

:::align{center} :::

注意： 这个 Google Doodle 与我们下面描述的贪吃蛇游戏规则并不完全一致，它仅用于让你对游戏的外观有一个大致概念。

Alex 刚学会编程，想开发他自己的贪吃蛇版本，规则如下：

• 游戏棋盘有 $R$ 行和 $C$ 列。棋盘的左上角格子坐标为 $(1, 1)$，右下角格子坐标为 $(R, C)$。
• 游戏开始时，在所有满足 $r + c$ 为奇数的坐标 $(r, c)$ 的格子里，都有一份食物。其他格子没有食物。
• 蛇的身体总是由棋盘上一个或多个格子构成的有序且连通的序列。序列的第一个格子被称为蛇的“头”。第二个格子（如果存在）与第一个格子共享一条边（而不仅仅是一个角），依此类推。序列的最后一个格子被称为蛇的“尾”。
• 蛇的头始终朝向四个方向之一：左、上、右或下。
• 游戏开始时，蛇位于格子 $(1, 1)$，长度为 $1$（即蛇仅由一个头组成），且头朝向右。
• 在每一个整数时刻（第 $1$ 秒，第 $2$ 秒等），蛇的头会向其头朝向的相邻格子移动。棋盘是循环的，也就是说，试图移出边界会导致头出现在棋盘的对面边界。例如，如果蛇在 $(1, C)$ 且头朝向右，则头下一步将移动到 $(1, 1)$。如果蛇在 $(1, C)$ 且头朝向上，则头下一步将移动到 $(R, C)$。
• 当蛇的头移动到一个没有食物的格子时，蛇不会增长。蛇的第二个格子（如果有）移动到蛇头原来所在的位置，蛇的第三个格子（如果有）移动到第二个格子原来所在的位置，依此类推。
• 当蛇的头移动到一个有食物的格子时，它会吃掉该食物（意味着该格子不再有食物），并且身体增长。在该食物所在的格子创建出一个新的头。原来蛇头所在的格子变成蛇的第二个格子，原来蛇的第二个格子（如果有）变成蛇的第三个格子，依此类推。
• 如果在一次移动完成后，蛇的头与它身体的其他某个格子处在同一位置，则蛇死亡，游戏立即结束。（注意：如果蛇的头朝它尾巴所在的格子移动，游戏不会结束，因为在移动完成之前尾巴会移开。）
• 在游戏中，玩家可以让蛇执行一些转向动作。每个动作 $A_i$ 会在第 $T_i$ 秒和第 $T_i+1$ 秒之间发生。有两种可能的动作："L" 和 "R"。"L" 动作会将头向左转 $90$ 度，例如，如果蛇原来朝向下，执行后它将朝向右。"R" 动作会将头向右转 $90$ 度，例如，如果蛇原来朝向下，执行后它将朝向左。
• 游戏有一个时间限制：在第 $10^9$ 秒的移动完成后（如果游戏能持续那么久的话！），游戏将结束。

为了测试游戏，Alex 编写了一系列 TURN 动作。你的任务是模拟这一系列动作，并告诉 Alex 游戏结束时蛇的最终长度。请记住，游戏可能因为一次移动完成后蛇的头与它身体的另一个格子重叠而结束，也可能因为时间耗尽而结束。在前一种情况下，为了计算长度，你应该将头部和与之重叠的身体那个格子视为两个独立的格子。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例以三个整数 $S$、$R$ 和 $C$ 开始，其中 $S$ 给出转向动作的数量，$R$ 和 $C$ 表示棋盘的行数和列数。紧接着是 $S$ 行；其中第 $i$ 行有一个整数 $X_i$，然后是一个字符 $A_i$，为 L 或 R。每一行对应在第 $X_i$ 秒和第 $X_i+1$ 秒之间执行的一个动作。数据保证这些动作是按时间顺序给出的，且同一秒之间永远不会有多于一个的动作。然而，你应该注意到，游戏可能在蛇执行完所有这些动作之前就结束了。

输出格式

对于每个测试用例，输出一行形如 Case #x: y 的内容，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是游戏结束时蛇的长度。

2
3 3 3
1 R
2 L
3 R
5 3 3
2 R
4 R
6 R
7 R
8 R

Case #1: 3
Case #2: 5

提示

限制

$1 \le T \le 10$。

小数据集（测试集 1 - 可见）

$1 \le R, C \le 100$； $1 \le S \le 100$； $1 \le X_i \le 2000$。

大数据集（测试集 2 - 可见）

$1 \le R, C \le 100000$； $1 \le S \le 100000$； $1 \le X_i \le 1000000$。

翻译由 DeepSeek V4 Pro 完成