3974: 「LibreOJ β Round #3」绯色 IOI（悬念）

> 考场的炸弹危机被成功解决了，元凶被绳之以法，IOI 顺利进行。Jsp 和 Rlc 利用最后的半小时 AK 了所有题并取得了前两名。 > > 今天是一个活动的日子，一向沉默的 Jsp 突然向 Rlc 提出了一个游戏。 > > 「怎么了，Jsp？」 > 「……」 > 「……」 > 「上次的问题，你的答案又是什么呢？」 Jsp 和 Rlc 的人格魅力吸引了世界各国的 IOI 选手来玩（\*）游（\*）戏（\*）。这其中有 $m$ 个妹子跟着 Rlc，编号为 $0,1,...,m-1$；有 $n$ 个男生跟着 Jsp，编号为 $0,1,...,n-1$。由于某些原因，总有 $m\leq n$，且 $n$ 是奇数。 现在 Rlc 准备让每个妹子选一个男生（当然，不包括 Jsp）作为同伴，一起学习 Chinese Data Structure。**两个妹子不能选择同一个男生**。 当然，由于语言障碍等原因妹子不是和所有男生都能愉快交流的。第 $i$ 个妹子能选择的男生可以由两个数 $a_i$ 和 $b_i$ 来描述： 对于 $0$ 到 $m-1$ 中的每个 $i$ 和 $0$ 到 $n-1$ 中的每个 $j$，若 $j$ 满足 $\min((j-a_i)\bmod n,(a_i-j)\bmod n)=b_i$（注意这里取模的值域是 $[0,n)$，如 $-1 \bmod 3 = 2$），则第 $i$ 个妹子和第 $j$ 个男生可以交流，称这对关系为 $(i,j)$。 Rlc 发现自己这边的妹子可以做到人人有同伴。但仅仅做到这一点是不行的，妹子和男生学习过程中的愉悦程度因人而异，Rlc 希望愉悦程度的总和最大。 不过某两人之间的愉悦程度有时会发生变化，这种变化一共有 $q$ 次。Rlc 用两个整数 $x,v$ 来描述变化，表示第 $x$ 对关系的愉悦程度变为 $v$。 Jsp 需要在一开始以及每次操作后回答：在所有妹子都有自己同伴的前提下，每一对同伴的愉悦程度的总和最大是多少。 有时为了强制 Jsp 按顺序回答，Rlc 会用上一次的答案加密自己对愉悦程度变化的描述。 --- **一句话题意**：在线动态维护一个二分图的最大权最大匹配。保证左侧满匹配。

第一行三个整数 $m,n,T$。其中 $T$ 表示加密参数。 接下来一行 $m$ 个整数 $a_0,a_1,...,a_{m-1}$。 接下来一行 $m$ 个整数 $b_0,b_1,...,b_{m-1}$。 接下来一行若干个整数 $v$，按编号从小到大依次表示每对关系的初始愉悦程度。 接下来一行一个整数 $q$。 接下来 $q$ 行每行两个整数 $x',v'$，表示加密后的描述。 解密方法是：设上次答案为 $\text{lastans}$，则真实的 $x=x'-\text{lastans}\cdot T,v=v'-\text{lastans}\cdot T$。保证这个关系存在。 每对关系 $(i,j)$ 按照**先 $i$ 后 $j$** 的顺序编号。即： ``` //no[i][j] 表示关系 (i,j) 的编号。 cnt = 0 for i = 0 to m - 1 do for j = 0 to n - 1 do if min((j - a[i]) mod n,(a[i] - j) mod n) = b[i] then no[i][j] := ++ cnt end if end for end for ```

输出共 $q+1$ 行，分别表示一开始以及每次修改后的答案。

8 9 0
5 6 2 0 1 5 7 3
4 4 1 4 4 1 0 4
3 2 4 1 0 0 2 0 3 2 5 4 2 3 1
9
3 0
2 4
3 6
6 6
5 12
11 8
13 4
14 9
15 0

19
16
17
21
27
28
29
31
31
30