给定一个长度为 $N$ 的整数序列 $A = (A_1, A_2, \dots, A_N)$，其中每个元素都是 $0$ 到 $M - 1$（包含 $0$ 和 $M - 1$）之间的整数。

你需要依次处理 $Q$ 个查询。第 $i$ 个查询描述如下：

• 给定整数 $x_i$ 和 $y_i$，将 $A$ 的第 $x_i$ 个元素更新为 $y_i$。更新后，解决以下问题：
  • 根据序列 $A$ 构建一个包含 $N$ 个顶点的无向图 $G$。顶点编号为 $1$ 到 $N$，当且仅当 $A_u + 1 \equiv A_v \pmod M$ 时，顶点 $u$ 和 $v$ ($1 \le u < v \le N$，注意 $u$ 和 $v$ 的顺序) 之间存在一条边。求图 $G$ 的最大匹配大小。

输入格式

输入通过标准输入按以下格式给出：

$N$ $M$ $Q$ $A_1$ $A_2$ $\dots$ $A_N$ $x_1$ $y_1$ $x_2$ $y_2$ $\vdots$ $x_Q$ $y_Q$

• $2 \le N \le 3 \times 10^5$
• $1 \le Q \le 3 \times 10^5$
• $2 \le M \le 3 \times 10^5$
• $0 \le A_i < M$
• $1 \le x_i \le N$
• $0 \le y_i < M$
• 所有输入值均为整数。

输出格式

输出 $Q$ 行。第 $i$ 行应包含第 $i$ 个查询的答案。

样例

输入 1

6 3 5
1 1 0 2 0 2
6 0
4 1
5 2
1 2
6 2

输出 1

1
1
2
3
3

说明

对于第一个查询，$A_6$ 被更新为 $0$，得到 $A = (1, 1, 0, 2, 0, 0)$。图 $G$ 在顶点对 $(1, 4), (2, 4), (4, 5)$ 和 $(4, 6)$ 之间有边。图 $G$ 的最大匹配大小为 $1$。

对于第二个查询，$A_4$ 被更新为 $1$，得到 $A = (1, 1, 0, 1, 0, 0)$。图 $G$ 在顶点对 $(3, 4)$ 之间有边。图 $G$ 的最大匹配大小为 $1$。