配点 : 1200 点
問題文
AtCoder 和 BatCoder 将展开一场企业大战。 AtCoder 有 编号至 1 它们的编号最大为 N 编号最多为 N 员工 i 的强度是 A_i,礼貌是 P_i 。 蝙蝠编码器也 1 它们的编号最大为 N 编号最多为 N 员工 i 的强度是 B_i 。
企业竞争是按以下步骤进行的事件。
- 首先,AtCoder 0 以上 N 的整数 声明 k 。
- 此后,两家公司都从实力较强的一家开始。 k 选择员工进行相互竞争(决胜局是可选的)。
- 本次企业竞赛得分为(AtCoder 参赛成员的实力总和)-(BatCoder 参赛成员的实力总和) 变为。
顺便说一句,AtCoder 正计划 我们安排了 Q 工作面试。 i 实力 X_i,礼貌 Y_i 候选人将会出现。 在这次面试之前,AtCoder 员工最起码的礼貌是什么? 比方说 z 。 如果 Y_i < z 如果是,则结束面试而不雇用该候选人。 如果 z < Y_i 然后雇用该候选人并 z 员工将被解雇。 请注意,在此问题中,仅给出所有字符都具有不同礼貌值的输入。 关于
各 t=0,1,\ldots,Q ,只是 t 第一轮面试结束后将进行公司间的竞争。 每个 求 t 企业竞赛的最高可能得分。
在这个问题中,X_i,Y_i 的值为 除非您在 t=i-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 值都不同
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N Q A_1 P_1 A_2 P_2 \vdots A_N P_N B_1 B_2 \ldots B_N X_1' Y_1' X_2' Y_2' \vdots X_Q' Y_Q'
在这里, 是X_i',Y_i' 是 X_i,Y_i 的加密值, 答案在0 \leq X_i',Y_i' < 2^{30} 很满意。 当 t=i-1 答案在 ans_{i-1} 然后,X_i,Y_i 的值可以如下恢复。
- X_i = X_i' \oplus (ans_{i-1} \pmod{2^{30}})
- Y_i = Y_i' \oplus (ans_{i-1} \pmod{2^{30}})
在这里, 是\oplus 以位为单位 \mathrm{XOR} 代表一个操作。 当
出力
Q+1 行。 i 行中,t=i-1 时打印答案。
入力例 1
3 1 3 0 1 1 4 2 3 0 3 3 1
出力例 1
2 1
- t=0:AtCoder 最好声明 k=3 。 AtCoder参赛成员的总实力为 4+3+1=8BatCoder参赛成员的总实力为 3+3+0=6 得分为 它变成 8-6=2 。
- 1 第二次采访: (X_i,Y_i)=(1,3) 。 AtCoder 是一种优势 3,礼貌 0 解雇员工并加强 雇用 1,礼貌 3 员工。
- t=1:AtCoder 最好声明 k=1 。 AtCoder参赛成员的总实力为 4BatCoder参赛成员的总实力为 3 得分为 它变成 4-3=1 。
入力例 2
6 5 12 4 11 15 0 6 4 0 8 5 4 8 2 8 8 13 7 6 9 1 5 8 0 9 15 12 4 2
出力例 2
2 6 2 0 5 5
入力例 3
10 13 92788721 542214255 293089679 516436321 669808382 626939225 238515753 666162008 242072611 97945595 466154699 275263259 1060112845 48898052 226548347 163247932 916132312 319810611 305065449 33194413 675278910 810708817 766536096 776055247 74986938 522734573 95413623 815637961 455070319 641005226 559678870 63240180 190319444 640573455 820546404 426868109 801203381 602683328 1028200997 844428795 592163827 328798860 890167861 914517637 1020849514 15202582 759333575 276170982 277756469 655405268 172240995 894346766 1012534420 985317173 392457922 844853509
出力例 3
349898379 471883737 187826139 415877835 572657577 572657577 572657577 335086730 209706130 195009665 195009665 107677877 273259909 273259909