小明爱玩一款即时战略游戏，里面需要农民来采集资源。小明控制的农民都很苦逼，所以被称作苦工。苦工采集木头会不间断送到主基地。因为需要掐准时间升级科技，而升级科技需要花费木头，所以小明经常需要知道某个时间段中苦工采集的木头总数是多少。他忙于操作他前线的部队，没有时间自己注意资源的变动情况，需要你帮他做一个程序能够实时回答小明提出的询问。
第一行给出一个正整数T(T<=10)，表示数据组数。
接下来对于每组数据，第一行首先给出两个正整数n和q(n,q<=10^5)，表示有n个时间点苦工把采集的木头送到了主基地，小明提出了q个询问。接下来n行，每一行给出一个格式为HH:MM:SS的时间，和一个正整数x(x<=10^4)表示该苦工该时刻送到主基地的木头数量，中间以空格分隔。接下来q行，每行两个时间点，格式为HH:MM:SS，中间用空格分隔，表示询问这两个时间点之间苦工送到主基地的木头总数，保证前者的时间点小于等于后者的时间点。（左右边界时刻送到的木头都算入总数）
输入保证时间格式合法，在00:00:00-23:59:59之间。并且00:00:00表示游戏开始，23:59:59表示游戏结束，同时这两个时间点也可能有木头采集送入基地。
可能存在一个时刻有多个苦工将木头送到主基地。
对于每组数据，每个询问，输出一个正整数，表示该时间段中采集木头的总量，占一行。
2
2 1
00:00:10 10
00:00:20 10
00:00:10 00:00:30
1 2
23:33:33 10
00:00:10 00:00:30
23:33:33 23:33:34
20
0
10
把时间转换为秒，int[]模拟dic，这个很简单。
如果把dic储存为那一个时刻时存放的数量，直接遍历时间段内所有的秒，其中可能有大量的0。储存需要10^5次加法，遍历最差需要24*3600*10^5次加法。
我的思路是记录下所有的送达记录，指定时间段只要计算范围内送达记录之和就行了。
但是这样其实有两个问题，一是送达记录可能不是递增的，可能需要排序一遍才行。第二个问题是，10^52>243600，最差情况下这种方法远比直接遍历秒要慢。
正确的解法是dic的每个元素都存放之前所有数量之和再加上当前的数量，每次存放时把当前及之后所有元素加指定数量，给出任意时间段后减一次就好了。最差时所有的都是0点送达，就需要做24*3600*10^5次加法；计算结果时需要10^5次减法。
总地来说，三种方法其实各有优劣。第一种的n无任何限制，而询问间隔×数量较小时才有优势。第三种的n分布多靠近末尾时可减少劣势，询问间隔和数量可任意，是优势；而如果输入的时间是排序好的，n的分布也可无限制。我的思路，只有n×询问数量较小时才有优势，n的分布和询问间隔无限制。