HZNUOJ

KK招新

Tags:   数据过大
Time Limit:  2 s      Memory Limit:   256 MB
Submission:435     AC:86     Score:95.71

Description

       单总在开完ACM宣讲会之后,有很多同学来问他能不能入队。单总便让TJ和KK负责招新。单总又有一个癖好,他想知道某一天以及之前一共来了多少人,而且他又想知道很多次,而TJ一个人统计不过来,她便去找她的男朋友CLD帮忙统计。但是单总询问的次数太多,以致于他们两人都忙不过来了,为了减轻女朋友的负担,CLD于是来找你帮忙了。

Input

每组输入数据的第一行含有一个正整数T,表示一共有T组测试数据。

每组测试数据的第一行含有一个正整数N, M, Q,表示一共有N天有人入队, 招新一共持续了M天, 单总有Q次询问。

接下来N行,每行包含两个正整数Di,Pi(1 <= i <= N),Di表示第几天,Pi表示当天入队多少人。

接下来Q行,每行包含一个正整数Ti(1 <= i <= Q), 表示单总想知道第Ti天以及之前一共入队了多少人。

数据范围:(1 <= T <= 10, 1 <= N <= M <= 100000, 1 <= Q <= 1000000, 1 <= Pi <= 1000000, 1 <= Di <= M)

Output

对于每一组数据,输出Q行,每一行表示单总想知道的第Ti天以及之前的入队总人数。

Samples

input
1 5 10 5 6 2 2 1 3 1 5 2 1 3 1 3 4 5 8
output
3 5 5 7 9

Hint

样例解释:
一共有5天有人新入队,招新一共持续了10天

显然, 第一天新入队三人

         第二天新入队一人

         第三天新入队一人

         第五天新入队俩人

         第六天新入队俩人

那么, 到第一天一共入队了三人

         到第三天一共入队了五人

         到第四天一共入队了五人

         到第五天一共入队了七人

         到第八天一共入队了九人

输入输出数据规模较大,建议使用C/C++的scanf以及printf提交

Author

PAN, Lyuzhi

Source

2018春学期ACM通识课期末考试