Background

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.

Problem Description

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.

Input Format

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 Format

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

2 3 2
2 0
2 3

3
2

Hint

Sample Explanation

After decrypting the sample:

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.

#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
template <typename T>
inline void read(T& r) {
	r=0;bool w=0; char ch=getchar();
	while(ch<'0'||ch>'9') w=ch=='-'?1:0,ch=getchar();
	while(ch>='0'&&ch<='9') r=r*10+(ch^48), ch=getchar();
	r=w?-r:r;
}

Translated by ChatGPT 5