AT_jsc2025_final_e Politeness Matters

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 $ での答えを求めるまでわかりません。 詳しくは入力セクションを確認してください。

入力は以下の形式で標準入力から与えられる。 > $ 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 $ のときの答えを出力せよ。

### Sample Explanation 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 $ になる。 ### Constraints - $ 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 $ の値はすべて異なる - 入力はすべて整数