一些城市沿着一条笔直的公路建造。
这些城市从左到右编号为 1,2,3......
有 N 个 G 巴士在这条路上运行。
对于每个 G 巴士,我们知道它服务的城市范围:第 i 个 g 巴士为编号为 Ai 和 Bi 之间的城市(包含 Ai 和 Bi)提供服务。
现在给定你一个城市子集 P。
对于 P 中包含的每一座城市,我们需要找出有多少辆 G 巴士为该城市服务。
第一行包含整数 T,表示共有 T 组测试数据。
每组数据第一行包含整数 N,表示 G 巴士的数量。
第二行包含 2N 个整数,形式为 A1 B1 A2 B2 A3 B3…AN BN,其中第 i 个 G 巴士服务于编号从 Ai 到 Bi(包括)的城市。
第三行包含整数 P,表示询问的城市数量。
接下来 P 行,每行包含一个整数 Ci,表示一个询问城市的编号。
每组数据之前隔一个空行。
每组数据输出一个结果,每个结果占一行。
结果表示为 Case #x: y,其中 x 是组别编号(从 1 开始),y 是 P 个空格隔开的整数,其中第 i 个整数是为城市 Ci 提供服务的 G 巴士的数量。
输入样例:
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中,有四个 G 巴士。
第一个服务城市 15 到 25,第二个服务城市 30 到 35,第三个服务城市 45 到 50,第四个服务城市 10 到 20。
城市 15 由第一个和第四个 G 巴士服务,城市 25 仅由第一个 G 巴士服务,因此答案输出为 2 1。
1≤T≤10 ,
1≤N≤5000 ,
1≤Ai,Bi,Ci≤10000 ,
1≤P≤5000