B - Miracle Dinner
問題文
prd レストランでは $N$ 個の料理と $M$ 個のデザートが用意されています。
最初、料理 $i$ のおいしさは $A_i$、デザート $j$ のおいしさは $B_j$ です。
prd 料理長は、料理 $i$ とデザート $j$ の組み合わせのうち、おいしさの和が $K$ の倍数になるものを「奇跡のディナー」と呼んでいます。
prd レストランでは、日々メニューの改変に取り組んでおり、毎日料理またはデザートのどれか $1$ つのおいしさを変更します。
$q$ 日目の変更は以下の通りです。
- $T_q = 1$ の場合、料理 $X_q$ のおいしさを $V_q$ に変更する
- $T_q = 2$ の場合、デザート $X_q$ のおいしさを $V_q$ に変更する
変更は永続的であることに注意してください。つまり、$q$ 日目の変更は $q+1$ 日目以降にも残り続けます。
$Q$ 日それぞれについて、おいしさ変更後における「奇跡のディナー」となる $(i,j)$ の組の個数を求めてください。
制約
- $1 \leq N,M,Q \leq 10^5$
- $1 \leq K,A_i,B_j,V_q \leq 10^9$
- $T_q \in \lbrace 1,2 \rbrace$
- $T_q = 1$ の場合 $1 \leq X_q \leq N$
- $T_q = 2$ の場合 $1 \leq X_q \leq M$
- 入力はすべて整数である。
部分点
この問題には部分点が設定されています。
- $Q = 1$ を満たすデータセットに正解すると、部分点として $150$ 点が与えられます。
入力
入力は以下の形式で標準入力から与えられます。
$N \space M \space Q \space K$
$A_1 \space \ldots \space A_N$
$B_1 \space \ldots \space B_M$
$T_1 \space X_1 \space V_1$
$\vdots$
$T_Q \space X_Q \space V_Q$
出力
$Q$ 行出力してください。
$q$ 行目には、$q$ 日目のおいしさ変更後の答えを出力してください。
5 4 4 5
1 2 4 5 9
3 6 7 8
1 1 10
2 3 15
1 5 13
2 1 20
4
6
5
6
$1$日目のおいしさを変更後、$A = (10,2,4,5,9), B = (3,6,7,8)$ となります。
このうち、条件を満たす $(i,j)$ は $(2,1), (2,4), (3,2), (5,2)$ の $4$個となります。
例えば、$(i,j) = (2,1)$ のとき、$A_2 + B_1 = 2 + 3 = 5$ で、$K=5$ の倍数です。
$2$日目のおいしさを変更後、$A = (10,2,4,5,9), B = (3,6,15,8)$ となります。
このうち、条件を満たす $(i,j)$ は $6$個となります。
$3$日目のおいしさを変更後、$A = (10,2,4,5,13), B = (3,6,15,8)$ となります。
このうち、条件を満たす $(i,j)$ は $5$個となります。
$4$日目のおいしさを変更後、$A = (10,2,4,5,13), B = (20,6,15,8)$ となります。
このうち、条件を満たす $(i,j)$ は $6$個となります。
6 6 1 2
3 1 4 1 5 9
2 7 1 8 2 8
2 6 9
18
このケースは部分点の制約を満たします。