众所周知，xbb喜欢吃甜的东西，越甜他就越喜欢吃。

现在有一个初始甜度为0的年糕条，xbb为了让自己吃的爽，他想要操作n次，每次操作xbb可以在年糕条任一位置x加上灵魂之汁让年糕的甜度在该位置上增加c。

但是在吃之前xbb需要经过年糕赞助商wwr的m次询问。每次询问wwr会给出两个数字l，r对应的xbb为了吃到食物需要回答出l，r范围内年糕的甜度和。

你能帮助xbb吗？

第一行包含两个整数n和m。

接下来n行，每行包含两个整数x和c。

再接下来m行，每行包含两个整数l和r。

−109≤x≤109,1≤n,m≤100000,
−109≤l<=r≤109,−10000≤c≤10000