「SvR-1」Five of Pentacles

UPD on 2023.2.5 by 出题人： 原题强制在线方式有问题，会使得一些依赖强制在线的方式通过，这并不是正解~~但是不想改了~~。

**请仔细阅读数据范围和时间限制。** 有一个长度为 $m$ 的数轴，一开始，处于 $1$ 时刻的**开始**，小 Z 处于 $1$ 号点，此时数轴上每个点都有一个障碍。 每个时刻，若小 Z 处于 $i$ 号点，小 Z 可以指定一个 $d \geq 0$，然后移动到 $i + d$ 号点，并且会越过 $[i, i + d]$ 的每一个障碍。 当然，一切都是在变化的，一共会有 $k$ 次变化，第 $i$ 次会发生如下变化： - $t_i$ 时刻内 $x_i$ 号点上的障碍将会消失。 - **请注意，此变化仅作用于 $t_i$ 时刻** 保证变化是**随时间倒序发生的**，也就是说 $t_i$ **单调不升**。 现在，对于每个 $1\le i\le k$，你都需要输出**在前 $i$ 个变化发生的条件下**、在保证第 $n$ 个时刻结束时小 Z 恰好处于 $m$ 号点的基础上，小 Z 越过的最小障碍数。

**本题强制在线，同时请注意在线形式。** 第一行，三个整数 $n,m,k$。 接下来 $k$ 行，其中第 $i$ 行有两个数字 $t_i, p$。其中 $p$ 用于生成 $x_i$，即：$x_i = \min(x_{i - 1} + p \oplus (lastans \bmod 15) + 1, m)$，其中 $lastans$ 表示上次变化的答案。 **特别地，第一次变化之前 $lastans = 0$，$x_0 = 0$，且当 $x_{i - 1} = m$ 时，将 $x_{i - 1}$ 视作 $0$（注意这不会真的改变 $x_{i - 1}$ 的值）。**

$k$ 行，每行一个整数，表示所求的值。

2 3 2
2 0
2 3

3
2

#### 样例解释 样例解密后： ```plain 2 3 2 2 1 2 2 ``` - 第一次变化后：小 Z 第一秒选择 $d = 0$，跨过一个障碍。第二秒选择 $d = 2$，原本跨过了 $3$ 个障碍，但是第 $2$ 秒第一个点没有障碍，所以只跨过了 $2$ 个障碍。一共 $1 + 2 = 3$ 个障碍。 - 第二次变化后：小 Z 第一秒选择 $d = 0$，跨过一个障碍。第二秒只有第三个位置有障碍，选择 $d = 2$，所以只跨过了一个障碍。一共 $1 + 1 = 2$ 个障碍。 #### 数据规模与约定 **本题自动开启捆绑测试和 O2 优化。** $$ \newcommand{\arraystretch}{1.5} \begin{array}{c|c|c}\hline\hline \textbf{Subtask} & \bm{n,m,k\le} & \textbf{分值} \\\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{无特殊限制} & 25 \\\hline\hline \end{array} $$ 对于 $100\%$ 的数据（解密后），$1 \leq n, m, k \leq 2 \times 10^6$，$1 \leq t_i \leq n$，$0 \leq p \leq 15$，$t_i$ **单调不升**，若 $t_i$ 相同，按 $x_i$ **升序**，且 $\forall 1 \leq i < j \leq k$，$(t_i, x_i)$ 和 $(t_j, x_j)$ 不同。 本题提供读入优化方式。 使用 `read(x);` 读入一个任意的整型 `x` 等价于 `scanf("%d", &x);`其中可以将 `%d` 自动识别为对应类型。 ```cpp #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; } ```