P8413 "SvR-1" Five of Pentacles

UPD on 2023.2.5 by the problem setter: The original forced-online method has issues, which allows some solutions that rely on the forced-online method to pass, and that is not the correct solution ~~but I do not want to change it~~.

**Please read the Constraints and time limit carefully.** There is a number line of length $m$. At the **start** of time $1$, Little Z is at position $1$, and at this moment, every position on the number line has an obstacle. At each moment, if Little Z is at position $i$, Little Z can choose a $d \geq 0$, then move to position $i + d$, and will cross over every obstacle in $[i, i + d]$. Of course, everything changes. There will be $k$ changes in total. The $i$-th change is as follows: - During time $t_i$, the obstacle at position $x_i$ will disappear. - **Note that this change only takes effect during time $t_i$.** It is guaranteed that the changes happen in **reverse chronological order**, that is, $t_i$ is **non-increasing**. Now, for each $1 \le i \le k$, you need to output, **under the condition that the first $i$ changes happen**, and with the requirement that at the end of time $n$ Little Z is exactly at position $m$, the minimum number of obstacles crossed by Little Z.

**This problem is forced-online. Please pay attention to the online format.** The first line contains three integers $n, m, k$. Then follow $k$ lines. On line $i$ there are two numbers $t_i, p$. Here $p$ is used to generate $x_i$, namely: $x_i = \min(x_{i - 1} + p \oplus (lastans \bmod 15) + 1, m)$, where $lastans$ denotes the answer of the previous change. **In particular, before the first change, $lastans = 0$, $x_0 = 0$, and when $x_{i - 1} = m$, treat $x_{i - 1}$ as $0$ (note that this will not actually change the value of $x_{i - 1}$).**

Output $k$ lines, each containing one integer, representing the required value.

#### Sample Explanation After decrypting the sample: ```plain 2 3 2 2 1 2 2 ``` - After the first change: In the first second, Little Z chooses $d = 0$ and crosses one obstacle. In the second second, Little Z chooses $d = 2$ and would originally cross $3$ obstacles, but in the second second, the first position has no obstacle, so only $2$ obstacles are crossed. In total, $1 + 2 = 3$ obstacles. - After the second change: In the first second, Little Z chooses $d = 0$ and crosses one obstacle. In the second second, only the third position has an obstacle, so choose $d = 2$, and only one obstacle is crossed. In total, $1 + 1 = 2$ obstacles. #### Data Scale and Notes **This problem automatically enables bundled testdata and O2 optimization.** $$ \newcommand{\arraystretch}{1.5} \begin{array}{c|c|c}\hline\hline \textbf{Subtask} & \bm{n,m,k\le} & \textbf{Score} \\\hline \textsf{1} & 100 & 15 \\\hline \textsf{2} & 2\times10^3 & 20 \\\hline \textsf{3} & 5\times10^4 & 20 \\\hline \textsf{4} & 10^6 & 20 \\\hline \textsf{5} & \text{No special constraints} & 25 \\\hline\hline \end{array} $$ For $100\%$ of the data (after decryption), $1 \leq n, m, k \leq 2 \times 10^6$, $1 \leq t_i \leq n$, $0 \leq p \leq 15$, $t_i$ is **non-increasing**; if $t_i$ are equal, sort by $x_i$ in **increasing** order; and for all $\forall 1 \leq i < j \leq k$, $(t_i, x_i)$ and $(t_j, x_j)$ are different. This problem provides an input optimization method. Using `read(x);` to read any integer `x` is equivalent to `scanf("%d", &x);`, where `%d` can be automatically recognized as the corresponding type. ```cpp #define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1