Description

哎？你看地上那是什么？好像是一张纸条。

亮晶晶的，散发着诡异的光。

子超好奇地捡起了纸条，下一瞬间！

“啊！！！我...我克制不住...”

纸条突然外放出声音，是某首知名音游神曲——（版权警告），同时吸附住了子超的手（其实是某人自己不放）。

华丽的摁动，精彩的手舞，只见子超精准的机械般完成了每一个指令，得到了无失误的最高分SSS。

“桀桀，不过如此。”

假设这张纸条长为n，子超在上面的每一次横向滑动，系统后台都会增加一个记忆值。

在曲目完成后，系统就会根据之前的记忆值，分析偏差，随机多次计算分数，问就是算着玩。

请你模拟出神奇纸条系统是如何运作的，然后给我也整一个。

Format

Input

第一行输入一个数n，代表纸条的长度。

第二行输入两个数，x和y，代表系统每次增加记忆值的个数和系统计算分数的次数。

之后 x 行每行输入三个数 l、r、c，系统给 l、r 这个范围内每一个位置增加 c 记忆值

最后 y 行每行输入两个数l、r，为曲目结束后每一次的分数计算，请给出l、r 这个范围内的记忆总和。

Output

输出占 y 行，每行一个记忆总和。

Samples

10
3 2
1 5 20
3 9 15
2 7 -11
1 8
5 10

124
62

Hint

数据范围：

1 <= n、x、y <= 10^5

1 <= l、r <= n

-10^9 <= c <= 10^9