金泽的地图

Time Limit: 3000 ms Memory Limit: 65536 KiB

Problem Description

 

 

在前往下一层的时候,金泽的地图不小心掉了出来,地图对于金泽来说是非常重要的,所以现在金泽感觉已经失去了人生的意义。

 

 

聪明的小千为了让失落的金泽开心一点,决定帮助金泽寻找他的地图。现在金泽想找到某些区域掉落了张多少地图,小千需要回答金泽的所有问题才能使金泽开心起来。

 

不过小千有点恐高,现在心情不是很好,无法完成计算,于是拜托你编写程序帮她完成这个任务。

现在小千给你了她的笔记,记录着每一块区域掉落了多少张地图,如果你完成了这个任务,小千将送给你一个Accepted!

 

 

 

现在我们简化一下问题,将掉落的区域视为一维的数轴。

小千的笔记记录着 N 条记录,格式为从 L 到 R 的闭区间里,每个位置掉落了 V 张地图。

金泽有 M 个提问,形式是从 L 到 R 的闭区间里,总共掉落了多少张地图。

Input

多组输入直到EOF结束。(数据组数 <= 5)

对于每组测试数据:

    第一行输入两个整数 N 和 M,代表小千的记录数和金泽的提问数。(1 <= N,M <= 100000)

    接下来 N 行,每行输入三个整数 li,ri,vi,代表从 li 到 ri 的闭区间里掉落了 vi 张地图。(1 <= li <= ri <= 100000,1 <= vi <= 100)

    接下来 M 行,每行输入两个整数 li,ri,代表金泽询问 li 到 ri 的闭区间里总共掉落了多少张地图。(1 <= li <= ri <= 100000)

Output

对每组数据的 M 次询问,输出 M 行,每行一个整数代表金泽询问的答案。

Sample Input

3 2
1 3 1
2 4 2
5 5 3
1 3
2 5

Sample Output

7
11

Hint

根据小千的记录,样例的状态应该是这样的:

1 位置掉落的地图数为:1

2 位置掉落的地图数为:1 + 2

3 位置掉落的地图数为:1 + 2

4 位置掉落的地图数为:2

5 位置掉落的地图数为:3

所以 [1, 3] 总共掉落的地图数为 1 + (1 + 2) + (1 + 2) = 7

[2, 5] 总共掉落的地图数为 (1 + 2) + (1 + 2) + 2 + 3 = 11

 

注意答案大小可能会超过 int

Source

Fish