踩气球

题目描述

六一儿童节到了, SHUXK 被迫陪着M个熊孩子玩一个无聊的游戏:有N个盒子从左到右排成一排,第i个盒子里装着$A_i$个气球。 SHUXK 要进行Q次操作,每次从某一个盒子里拿出一个没被踩爆的气球,然后熊孩子们就会立刻把它踩爆。 这M个熊孩子每个人都指定了一个盒子区间[$L_i$,$R_i$]。 如果某一个时刻,一个熊孩子发现自己选定的盒子区间[$L_i$,$R_i$]中的所有气球都已经被踩爆了,他就会非常高兴(显然之后他一直会很高兴)。 为了不辜负将自己的任务强行塞给 SHUXK 的那个人的期望, SHUXK 想向你询问: 他每次操作过后会有多少个熊孩子很高兴。

输入输出格式

输入格式


第一行包含两个正整数N和M,分别表示盒子和熊孩子的个数。 第二行包含N个正整数Ai( 1<=$A_i$<=$10^5$),表示每个盒子里气球的数量。 以下M行每行包含两个正整数Li, Ri( 1<=$L_i$<=$R_i$<=N),分别表示每一个熊孩子指定的区间。 以下一行包含一个正整数Q,表示 SHUXK 操作的次数。 以下Q行每行包含一个正整数X,表示这次操作是从第X个盒子里拿气球。为了体现在线,我们对输入的X进行了加密。 假设输入的正整数是$\hat{x}$,那么真正的X=($\hat{x}$+Lastans−1)Mod N +1。其中Lastans为上一次询问的答案。对于第一个询问, Lastans=0。 输入数据保证1<=$\hat{x}$<=$10^9$, 且第X个盒子中有尚未被踩爆的气球。 N<=$10^5$,M<=$10^5 $,Q<=$10^5$

输出格式


包含Q行,每行输出一个整数,表示 SHUXK 一次操作后询问的答案。答案的顺序应与输入数据的顺序保持一致。

输入输出样例

输入样例 #1

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

输出样例 #1

0 
1 
1 
2 
3