[HNOI/AHOI2018]转盘

题目描述

一次小 G 和小 H 准备去聚餐,但是由于太麻烦了于是题面简化如下: 一个转盘上有摆成一圈的 $n$ 个物品(编号 $1\sim n$),其中的 $i$ 个物品会在 $T_i$ 时刻出现。 在 $0$ 时刻时,小 G 可以任选 $n$ 个物品中的一个,我们将其编号为 $s_0$。并且如果 $i$ 时刻选择了物品 $s_i$,那么 $i+1$ 时刻可以继续选择当前物品或选择下一个物品。当 $s_i$ 为 $n$ 时,下一个物品为物品 $1$,否则为物品 $s_{i}+1$。在每一时刻(包括0时刻),如果小 G 选择的物品已经出现了,那么小 G 将会标记它。小 H 想知道,在物品选择的最优策略下,小 G 什么时候能标记所有物品? 但麻烦的是,物品的出现时间会不时修改。我们将其描述为 $m$ 次修改,每次修改将改变其中一个物品的出现时间。每次修改后,你也需求出当前局面的答案。对于其中部分测试点,小 H 还追加了强制在线的要求。

输入输出格式

输入格式


第一行三个非负整数 $n$、$m$、$p$,代表一共有 $n$ 个物品,$m$ 次修改。$p$ 只有 $0$ 或 $1$ 两种取值,强制在线时 $p$ 为 $1$,否则 $p$ 为 $0$。 接下来一行,有 $n$ 个**非负整数**,第 $i$ 个数 $T_i$ 代表物品 $i$ 的出现时间。 接下来 $m$ 行,每行两个非负整数 $x$、$y$,代表一次修改及询问。修改方式如下: 1. 如果 $p=0$,则表示物品 $x$ 的出现时间 $T_x$ 修改为 $y$。 2. 如果 $p=1$,则先将 $x$ 和 $y$ 分别异或 $LastAns$,得到 $x'$ 和 $y'$,然后将物品 $x'$ 的出现时间 $T_{x'}$ 修改为 $y'$。其中的 $LastAns$ 是前一个询问的结果;特别的,第一次修改时 $LastAns$ 为初始局面的答案。 保证输入合法。

输出格式


第一行一个整数,代表初始局面的答案。 接下来 $m$ 行每行一个整数,分别代表每次修改后的答案。

输入输出样例

输入样例 #1

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

输出样例 #1

5
7
6
7

说明

![](https://cdn.luogu.com.cn/upload/pic/17510.png)