说明

“再往北二百里，是座发鸠山，山上生长着茂密的柘树。山中有一种禽鸟，形状像一般的乌鸦，却长着花脑袋、白嘴巴、红足爪，名称是精卫，它发出的叫声就是自身名称的读音。精卫鸟原是炎帝的小女儿，名叫女娃。女娃到东海游玩。淹死在东海里没有返回，就变成了精卫鸟，常常衔着西山的树枝和石子，用来填塞东海。漳水从这座山发源，向东流入黄河。”

东东合上了故事书，“今天的故事就先讲到这里吧。”

“那故事的结局呢？最后小精卫有成功填上东海么？”瑶瑶小盆友好奇地问道。

东东笑着摇了摇头，但小瑶瑶并没有放弃追问。“那么多的石头树枝扔进去，短时间内海面的高度总会有起伏变化的吧。”

“我知道我要做什么啦！我想要知道故事结束后海面某个位置具体的高度！”话音刚落，小瑶瑶便兴奋地跑开了。

而与此同时，路过的磊哥听完他们的对话，拿出草稿纸开始演算起来：

假设海水总体积不变，将海面置于平面坐标系中，初始的海面（精卫还未在东海玩耍时）高度y为0，海面范围为[0,n]。

接下来（精卫溺亡后），精卫来回从西山飞了m次，每次衔来密度为q的石子或树枝，飞到海面位置x处的上空扔下，而x处产生的能量以波的形式向周围传播。

每一次投掷会导致x处高度直接降低了q，而从x-1到x-q和x+1到x+q高度降低且减少的高度依次递减（q-1 -> 0）,再从x-q-1到x-2q和x+q+1到x+2q高度升高且增加的高度依次递增（1 -> q）,从x-2q到x-3q+1和x+2q到x+3q-1高度升高且增加的高度依次递减（q -> 1）。每次投掷所产生的影响独立可叠加。

如图：设q=2，则海面发生如下变化：

在经历一番演算后，磊哥惊奇地发现，一颗小小的石子竟能产生如此大的影响，而且对海面上升的积极影响要大于消极影响。难不成，最后精卫真的能做到填海？

现在东东，瑶瑶和磊哥都很想知道在精卫填海后短时间内海面某个位置的高度，请你快帮帮他们吧！

输入格式

输入第一行给出一个整数n（1<=n<=1e6）,表示海面范围为[0,n];

随后的一行给出一个整数m（1<=m<=1e6）,表示精卫投掷的次数;

接下来m行，每一行包括两个整数x，q，分别表示投掷位置x（0<=x<=n）和投掷物的密度q（0<=q<=1e6）;

随后的一行给出一个整数k(1<=k<=n+1),表示有k次询问;

接下来k行，每一行包括一个整数y(0<=y<=n),表示所查询的位置。

输出格式

准确输出k行，每行包括所查询位置的高度。请不要输出多余空格。

样例

10
1
5 1
10
1
2
3
4
5
6
7
8
9
10

0
0
1
0
-1
0
1
0
0
0

提示

None