踩气球
题目描述
六一儿童节到了,SHUXK 被迫陪着 $m$ 个熊孩子玩一个无聊的游戏:有 $n$ 个盒子从左到右排成一排,第 $i$ 个盒子里装着 $a_i$ 个气球。
SHUxK 要进行 $Q$ 次操作,每次从某一个盒子里拿出一个没被踩爆的气球,然后熊孩子们就会立刻把它踩爆。
这 $m$ 个熊孩子每个人都指定了一个盒子区间 $[l_i,r_i]$。如果某一个时刻,一个熊孩子发现自己选定的盒子区间 $[l_i,r_i]$ 中的所有气球都已经被踩爆了,他就会非常高兴(显然之后他一直会很高兴)。
为了不辜负将自己的任务强行塞给 SHUXK 的那个人的期望,SHUXK 想向你询问:
- 他每次操作过后会有多少个熊孩子很高兴。
输入输出格式
输入格式
第一行包含两个正整数 $n$ 和 $m$,分别表示盒子和熊孩子的个数。
第二行包含 $n$ 个正整数 $a_i$($1 \le a_i \le 10^5$),表示每个盒子里气球的数量。
以下 $m$ 行每行包含两个正整数 $l_i,r_i$($1 \le l_i \le r_i \le n$),分别表示每一个熊孩子指定的区间。
以下一行包含一个正整数 $Q$,表示 SHUXK 操作的次数。
以下 $Q$ 行每行包含一个正整数 $x$,表示这次操作是从第 $x$ 个盒子里拿气球。为了体现在线,我们对输入的 $x$ 进行了加密。
假设输入的正整数是 $\hat{x}$,那么真正的 $x=(\hat{x}+\mathit{lastans}-1)\bmod n+1$。其中 $\mathit{lastans}$ 为上一次询问的答案。对于第一个询问,$\mathit{lastans}=0$。
输出格式
包含 $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
说明
### 数据范围及约定
对于全部数据,$1\le n \le 10^5$,$1\le m \le 10^5$,$1\le Q \le 10^5$。
输入数据保证 $1 \le \hat{x} \le 10^9$,且第 $x$ 个盒子中有尚未被踩爆的气球。