D. 绯色 IOI（悬念）

Jsp 和 Rlc 的人格魅力吸引了世界各国的 IOI 选手来玩（*）游（*）戏（*）。这其中有 个妹子跟着 Rlc，编号为 ；有 个男生跟着 Jsp，编号为 。由于某些原因，总有 ，且 是奇数。

现在 Rlc 准备让每个妹子选一个男生（当然，不包括 Jsp）作为同伴，一起学习 Chinese Data Structure。两个妹子不能选择同一个男生。

当然，由于语言障碍等原因妹子不是和所有男生都能愉快交流的。第 个妹子能选择的男生可以由两个数 和 来描述：

对于 到 中的每个 和 到 中的每个 ，若 满足 （注意这里取模的值域是 ，如 ），则第 个妹子和第 个男生可以交流，称这对关系为 。

Rlc 发现自己这边的妹子可以做到人人有同伴。但仅仅做到这一点是不行的，妹子和男生学习过程中的愉悦程度因人而异，Rlc 希望愉悦程度的总和最大。

不过某两人之间的愉悦程度有时会发生变化，这种变化一共有 次。Rlc 用两个整数 来描述变化，表示第 对关系的愉悦程度变为 。

Jsp 需要在一开始以及每次操作后回答：在所有妹子都有自己同伴的前提下，每一对同伴的愉悦程度的总和最大是多少。

有时为了强制 Jsp 按顺序回答，Rlc 会用上一次的答案加密自己对愉悦程度变化的描述。

一句话题意：在线动态维护一个二分图的最大权最大匹配。保证左侧满匹配。

第一行三个整数 。其中 表示加密参数。
接下来一行 个整数 。
接下来一行 个整数 。
接下来一行若干个整数 ，按编号从小到大依次表示每对关系的初始愉悦程度。
接下来一行一个整数 。
接下来 行每行两个整数 ，表示加密后的描述。
解密方法是：设上次答案为 ，则真实的 。保证这个关系存在。

每对关系 按照先 后 的顺序编号。即：

//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

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

样例输入 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

样例输出 1

19
16
17
21
27
28
29
31
31
30

样例解释 1

样例中描述的二分图如下：

样例输入 2

6 9 1
5 1 2 0 1 3 
4 0 0 4 4 4 
13 19 17 6 4 16 0 4 13 8 
9
75 70
60 70
55 59
59 65
69 74
79 70
70 77
69 72
73 77

样例输出 2

69
57
53
53
61
70
65
65
66
66

对于所有数据， 是奇数 ，任何时刻每对关系的愉悦程度是 中的整数。

数据保证存在一个匹配使得每个妹子都能找到自己的伙伴。