题目背景

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

提示

样例解释

样例解密后：

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 自动识别为对应类型。

#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;
}