题目描述

Circleburg 市有一条大的环形街道，沿街有 $N$ 个领事馆。领事馆按顺时针顺序编号为 $1, 2, \dots, N$。

今天，有 $G$ 位客人（编号 $1, 2, \dots, G$）将沿着环形街道行驶 $M$ 分钟。每位客人要么是顺时针客人（用字符 C 表示），要么是逆时针客人（用字符 A 表示）。

第 $i$ 位客人从编号为 $H_i$ 的领事馆出发，每分钟结束时都会行驶到相邻的领事馆。如果该客人是：

• 顺时针客人，则行驶到 $(j+1)$ 号领事馆（若当前在 $N$ 号，则行驶到 $1$ 号）；
• 逆时针客人，则行驶到 $(j-1)$ 号领事馆（若当前在 $1$ 号，则行驶到 $N$ 号）。

每个领事馆只会记住最后访问它的客人。如果有多个客人在最后时刻同时访问，则该领事馆会记住所有这些客人。

对于每位客人，请计算有多少个领事馆会记住他们。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含三个整数 $N$、$G$ 和 $M$，分别表示领事馆的数量、客人的数量以及行驶的分钟数。随后 $G$ 行，第 $i$ 行包含整数 $H_i$ 后跟一个字符：若第 $i$ 位客人是顺时针客人则为 C，逆时针则为 A。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y_1 y_2 ... y_G，其中 $x$ 是测试用例编号（从 $1$ 开始），$y_i$ 是第 $i$ 位客人被记住的领事馆数量。

4
5 3 2
5 C
2 A
1 A
2 4 0
1 A
1 C
1 A
1 C
3 2 10
3 C
2 A
6 1 6
4 A

Case #1: 2 2 1
Case #2: 1 1 1 1
Case #3: 2 2
Case #4: 6

提示

在第一个样例中，有 $N = 5$ 个领事馆，$G = 3$ 位客人，行驶 $M = 2$ 分钟。

• 对于第 1 个领事馆，最后访问它的客人是客人 1 和客人 2（在第 1 分钟结束时）。
• 对于第 2 个领事馆，最后访问它的客人是客人 1（在第 2 分钟结束时）。
• 第 3 个领事馆从未被访问。
• 对于第 4 个领事馆，最后访问它的客人是客人 3（在第 2 分钟结束时）。
• 对于第 5 个领事馆，最后访问它的客人是客人 2（在第 2 分钟结束时）。

因此，第 1、2、3 位客人对应的答案分别是 2、2、1。

在第二个样例中，有 $N = 2$ 个领事馆，$G = 4$ 位客人，行驶 $M = 0$ 分钟。

• 对于第 1 个领事馆，最后访问它的客人是客人 1、2、3 和 4（所有客人都从此领事馆出发）。
• 第 2 个领事馆从未被访问。

因此，第 1、2、3、4 位客人对应的答案分别是 1、1、1、1。

在第三个样例中，有 $N = 3$ 个领事馆，$G = 2$ 位客人，行驶 $M = 10$ 分钟。

• 对于第 1 个领事馆，最后访问它的客人是客人 1 和客人 2（在第 10 分钟结束时）。
• 对于第 2 个领事馆，最后访问它的客人是客人 2（在第 9 分钟结束时）。
• 对于第 3 个领事馆，最后访问它的客人是客人 1（在第 9 分钟结束时）。

因此，第 1 和 2 位客人对应的答案分别是 2、2。

在第四个样例中，只有一位客人。这位客人最终会访问所有领事馆，因此所有领事馆都记住了他。所以答案为 6。

限制条件

$1 \le T \le 100$。

对于所有 $i$，$1 \le H_i \le N$。

测试集 1（可见）

$2 \le N \le 100$。

$1 \le G \le 100$。

$0 \le M \le 100$。

测试集 2（隐藏）

$2 \le N \le 10^5$。

$1 \le G \le 10^5$。

$0 \le M \le 10^9$。

翻译由 DeepSeek V4 Pro 完成