P16733 [GKS 2019 #D] Latest Guests

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$ 位客人被记住的领事馆数量。

在第一个样例中，有 $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 完成