/ 
Time Limit: 4 sec / Memory Limit: 1024 MiB
配点 : 1200 点
問題文
AtCoder 社と BatCoder 社が企業対抗戦を行います。 AtCoder 社には 1 から N までの番号がついた N 人の社員がおり、社員 i の強さは A_i、礼儀正しさは P_i です。 BatCoder 社にも 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=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 を宣言するのが最適である。 AtCoder 社の対戦メンバーの強さの総和は 4、BatCoder 社の対戦メンバーの強さの総和は 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