小 P は生活の中の様々な問題を研究するのが好きで、最近は「入浴」という問題について深く研究しています。小 P が住む寮の階には $m$ 個のシャワーブース（同時に $m$ 人が入浴可能）があり、毎日 $n$ 人が入浴を希望しています。各人が入浴に向かう時刻は $t_i$ であり、入浴にかかる時間は一律で $T$ です。

第 $i$ 番目の人が時刻 $t_i$ に入浴しに行き、もし空いているブースがなければ、誰かが入浴を終えるまで待つ必要があります。誰かが入浴を終えると、その人は直ちに入浴を開始します。

第 $i$ 番目の人が最終的に入浴を開始する時刻を $s_i$ とすると、その人の不満度は $s_i - t_i$ となります。

これからの $q$ 日間について、第 $j$ 日目には $x_j$ 番目の人の入浴予定時刻が $t'_j$ に変更されます。なお、第 $j$ 日目の変更は第 $j+1$ 日目には引き継がれません。

小 P は不満度の合計に興味があるため、各日について全員の不満度の合計を求めてください。

入力

入力は以下の形式で与えられます。

$n \ m \ q \ T$ $t_1 \ t_2 \ \dots \ t_n$ $x_1 \ t'_1$ $x_2 \ t'_2$ $\vdots$ $x_q \ t'_q$

1 行目には 4 つの正整数 $n, m, q, T$ が与えられ、それぞれ入浴人数、シャワーブースの数、クエリ回数、固定の入浴時間を表します。

続く 1 行には $n$ 個の正整数が与えられ、第 $i$ 番目の正整数 $t_i$ は第 $i$ 番目の人が入浴に向かう時刻を表します。すべての $i \in [1, n)$ に対して $t_i \le t_{i+1}$ であることが保証されます。

続く $q$ 行には、各日における変更が与えられます。各行は 2 つの整数 $x_j, t'_j$ であり、第 $x_j$ 番目の人の入浴時刻がその日（その日のみ）$t'_j$ に変更されることを表します。

出力

合計 $q$ 行出力してください。第 $j$ 行には、第 $j$ 日目における不満度の合計を出力してください。

入出力例

入力 1

10 3 5 7
1 1 1 2 6 9 12 13 15 17 
8 6
2 14
7 10
9 17
6 16

出力 1

24
15
21
18
18

入力 2

12 2 10 8
4 4 5 9 10 11 14 14 15 19 23 23 
10 1
9 14
7 6
10 9
1 10
4 1
11 15
3 20
9 8
10 20

出力 2

137
138
145
147
137
127
145
122
144
136

制約

すべてのデータにおいて、$1 \le m \le 5, 1 \le n \le 10^6, 1 \le q \le 10^5, 1 \le t_i, T \le 10^8$ を満たします。