P4215 Popping Balloons

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?

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 $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.

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