无限之路
题号:NC214613
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

无限之路

我们趋行在人生这个亘古的旅途,在坎坷中奔跑,在挫折里涅盘,忧愁缠满全身,痛苦飘洒一地。我们累,却无从止歇;我们苦,却无法回避。人生的路还很长,心中的梦想还在远方,无牵无挂便可自由飞翔,不怕意外折断了翅膀,相信自己有重生的力量,坚守的方向,曾经的信仰,拾起不忘,若前路无光,请用灵魂照亮,若前路漫长,请用一生守望,我是一名过客在世界上,路很长,在风的那方。

繁凡 漫步在一条名叫人生的无限之路上,这条路可以看成是一条无限长的数轴,数轴的每个坐标上都有一个荣誉值,我们每个人来到这个世界,就像一张白纸,等待着我们亲手书写属于自己的传奇,因此最初数轴的每个坐标上的荣誉值都为

经过不懈的努力,繁凡さん 获得了 次荣誉,每次获得荣誉就会在数轴的坐标 上增加权值为 的荣誉值。

人最宝贵的东西是生命。生命对人来说只有一次。因此,人的一生应当这样度过:当一个人回首往事时,不因虚度年华而悔恨,也不因碌碌无为而羞愧。 —— 《钢铁是怎样炼成的》

回顾过往,繁凡想知道自己在 之间共获得了多少的荣誉值,所以他会给你 次询问,每个询问包含两个整数 ,你需要求出数轴的坐标在区间 之间的荣誉值之和。



输入描述:

第一行包含两个整数  和  。

接下来  行,每行包含两个整数  和 

再接下里  行,每行包含两个整数  和 

输出描述:

行,每行输出一个询问中所求的区间内荣誉值之和。
示例1

输入

复制
3 3
1 2
3 6
7 5
1 3
4 6
7 8

输出

复制
8
0
5

备注:

数据范围

数据很大,数组不可能存得下,可以考虑离散所有的数据,将所有数据离散化