小 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$，表示洗澡人數、澡堂個數、詢問次數，以及洗澡的固定時間。

接下來的一行有 $n$ 個正整數，第 $i$ 個正整數 $t_i$ 表示第 $i$ 個人前去洗澡的時間，保證 $\forall i\in [1,n),t_i\le t_{i+1}$。

接下來的 $q$ 行，每行兩個整數 $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$。