题目描述

有一些城市沿着一条笔直的公路而建。这些城市从左到右依次编号为 $1$、$2$、$3$……

有 $N$ 辆 GBus 在这条公路上运行。对于每辆 GBus，我们知道它服务的城市范围：第 $i$ 辆 GBus 服务的城市编号在 $A_i$ 到 $B_i$ 之间（包含两端）。

我们关心其中特定的 $P$ 个城市。对于这些城市中的每一个，我们需要找出有多少辆 GBus 为它服务。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来是 $T$ 个测试用例；每个测试用例之间由一个空行分隔。（请注意，这对 Kickstart 数据集来说是不常见的。）

在每个测试用例中：

• 第一行包含一个整数 $N$：GBus 的数量。
• 第二行包含 $2N$ 个整数，以 $A_1 \ B_1 \ A_2 \ B_2 \ A_3 \ B_3 \dots A_N \ B_N$ 的形式给出各公交线路服务的城市范围。也就是说，第一辆 GBus 服务编号从 $A_1$ 到 $B_1$（含）的城市，依此类推。
• 第三行包含一个整数 $P$：如上所述，我们关心的城市数量。（注意，这个数不一定等于问题中的城市总数，后者并未给出。）
• 最后，还有 $P$ 行；其中第 $i$ 行包含我们所关心的一个城市的编号 $C_i$。

输出格式

对于每个测试用例，输出一行形如 Case #x: y 的内容，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是一个包含 $P$ 个整数的列表，其中的第 $i$ 个整数表示服务城市 $C_i$ 的 GBus 的数量。

2
4
15 25 30 35 45 50 10 20
2
15
25
10
10 15 5 12 40 55 1 10 25 35 45
50 20 28 27 35 15 40 4 5
3
5
10
27

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

提示

在样例用例 #1 中，共有四辆 GBus。第一辆服务城市 $15$ 至 $25$，第二辆服务城市 $30$ 至 $35$，第三辆服务城市 $45$ 至 $50$，第四辆服务城市 $10$ 至 $20$。城市 $15$ 同时被第一辆和第四辆服务，因此答案列表中的第一个数字是 $2$。城市 $25$ 仅被第一辆服务，因此答案列表中的第二个数字是 $1$。

限制

$1 \le T \le 10$。

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

$1 \le N \le 50$

对于所有 $i$，$1 \le A_i \le 500$。

对于所有 $i$，$1 \le B_i \le 500$。

对于所有 $i$，$1 \le C_i \le 500$。

$1 \le P \le 50$。

大数据集（测试集 2 - 隐藏）

$1 \le N \le 500$。

对于所有 $i$，$1 \le A_i \le 5000$。

对于所有 $i$，$1 \le B_i \le 5000$。

对于所有 $i$，$1 \le C_i \le 5000$。

$1 \le P \le 500$。

翻译由 DeepSeek V4 Pro 完成