AT_jsc2025_final_e.Politeness Matters

AtCoder 社与 BatCoder 社进行企业对抗赛。AtCoder 社有 $N$ 名员工，编号为 $1$ 到 $N$，第 $i$ 号员工的强度为 $A_i$，礼仪分为 $P_i$。BatCoder 社同样有 $N$ 名员工，编号 $1$ 到 $N$，第 $i$ 号员工的强度为 $B_i$。

企业对抗赛按照以下方式进行：

• 首先，AtCoder 社宣布一个整数 $k$，满足 $0 \leq k \leq N$。
• 随后，两家公司各自选择强度最大的 $k$ 名员工作为出战成员（若强度相同，任意选取）。
• 这场企业对抗赛的得分为：$(\text{AtCoder 社成员强度之和}) - (\text{BatCoder 社成员强度之和})$。

接下来，AtCoder 社有 $Q$ 场招聘面试。第 $i$ 场面试时，出现一名候选人，强度为 $X_i$，礼仪分为 $Y_i$。在本次面试前，AtCoder 社员工的礼仪分最小值为 $z$。若 $Y_i < z$，则不录用该候选人；若 $Y_i > z$，则录用该候选人，并解雇礼仪分为 $z$ 的员工。题目保证所有员工及候选人的礼仪分都互不相同。

对于每个 $t=0,1,\ldots,Q$，即完成前 $t$ 场面试后，举行企业对抗赛。请你计算每个 $t$ 时最大可能的企业对抗赛得分。

此外，本题 $X_i,Y_i$ 的值只有在求出 $t=i-1$ 时的答案后，才能通过如下方式恢复。请参见输入格式。

输入从标准输入读取，格式如下：

$N$ $Q$
$A_1$ $P_1$
$A_2$ $P_2$
⋮
$A_N$ $P_N$
$B_1$ $B_2$ ⋯ $B_N$
$X_1'$ $Y_1'$
$X_2'$ $Y_2'$
⋮
$X_Q'$ $Y_Q'$

其中，$X_i',Y_i'$ 是 $X_i,Y_i$ 的加密值，满足 $0 \leq X_i',Y_i' < 2^{30}$。令 $ans_{i-1}$ 表示 $t=i-1$ 时的答案，则 $X_i,Y_i$ 可按如下方式恢复：

• $X_i = X_i' \oplus (ans_{i-1} \bmod 2^{30})$
• $Y_i = Y_i' \oplus (ans_{i-1} \bmod 2^{30})$

其中，$\oplus$ 表示按位异或运算。

输出 $Q+1$ 行。第 $i$ 行输出 $t=i-1$ 时的答案。

样例解释 1

• $t=0$：AtCoder 社选择 $k=3$ 最优。AtCoder 社成员强度之和为 $4+3+1=8$，BatCoder 社为 $3+3+0=6$，得分为 $8-6=2$。
• 第 $1$ 次面试：$(X_i, Y_i) = (1, 3)$。AtCoder 社解雇强度 $3$、礼仪分 $0$ 的员工，录用强度 $1$、礼仪分 $3$ 的新人。
• $t=1$：AtCoder 社选择 $k=1$ 最优，强度为 $4$，BatCoder 社为 $3$，得分 $4-3=1$。

数据范围

• $1 \leq N \leq 250000$
• $1 \leq Q \leq 250000$
• $0 \leq A_i, B_i, P_i, X_i, Y_i < 2^{30}$
• $P_1,\ldots,P_N, Y_1,\ldots,Y_Q$ 均互不相同
• 所有输入均为整数

由 ChatGPT 5 翻译