Description

Children’s Day has arrived, and SHUXK is forced to play a boring game with $m$ kids: there are $n$ boxes lined up from left to right, and the $i$-th box contains $a_i$ balloons.

SHUXK will perform $Q$ operations. In each operation, he takes one unpopped balloon from some box, and the kids immediately pop it.

Each of the $m$ kids has specified an interval of boxes $[l_i, r_i]$. If at any moment a kid finds that all balloons in their chosen interval $[l_i, r_i]$ have been popped, they become very happy (and will remain happy thereafter).

To live up to the expectations of the person who dumped this task on SHUXK, he asks you:

• After each operation, how many kids are happy?

Input Format

The first line contains two positive integers $n$ and $m$, the numbers of boxes and kids, respectively.

The second line contains $n$ positive integers $a_i$ ($1 \le a_i \le 10^5$), the number of balloons in each box.

Each of the following $m$ lines contains two positive integers $l_i, r_i$ ($1 \le l_i \le r_i \le n$), the interval specified by each kid.

The next line contains a positive integer $Q$, the number of operations SHUXK performs.

Each of the following $Q$ lines contains a positive integer $x$, indicating that this operation takes a balloon from the $x$-th box. To enforce online queries, the input $x$ is encrypted.

Let the given positive integer be $\hat{x}$; then the real $x=(\hat{x}+\mathit{lastans}-1)\bmod n+1$, where $\mathit{lastans}$ is the answer to the previous query. For the first query, $\mathit{lastans}=0$.

Output Format

Output $Q$ lines. Each line should contain one integer, the answer to SHUXK’s question after a single operation. The answers must be in the same order as the input queries.

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

0 
1 
1 
2 
3

Hint

Constraints and Conventions

For all data, $1 \le n \le 10^5$, $1 \le m \le 10^5$, $1 \le Q \le 10^5$.

The testdata guarantees $1 \le \hat{x} \le 10^9$, and that the $x$-th box always has at least one unpopped balloon.

Translated by ChatGPT 5