Mały P lubi badać różnorodne problemy z życia codziennego, a ostatnio zainteresował się kwestią korzystania z łaźni. W akademiku, w którym mieszka Mały P, łaźnia posiada $m$ stanowisk (co oznacza, że $m$ osób może korzystać z kąpieli jednocześnie). Każdego dnia $n$ osób chce skorzystać z łaźni, a czas przybycia $i$-tej osoby to $t_i$. Czas trwania kąpieli dla każdej osoby jest stały i wynosi $T$.

Jeśli $i$-ta osoba przychodzi do łaźni w momencie $t_i$ i nie ma wolnego stanowiska, musi poczekać, aż ktoś inny skończy kąpiel. Gdy tylko zwolni się stanowisko, osoba ta natychmiast rozpoczyna kąpiel.

Załóżmy, że $s_i$ to moment, w którym $i$-ta osoba faktycznie rozpoczyna kąpiel. Wówczas generuje ona niezadowolenie równe $s_i - t_i$.

W ciągu kolejnych $q$ dni, w dniu $j$, osoba $x_j$ zmienia swój plan i jej czas przybycia zmienia się na $t'_j$. Zauważ, że zmiana w dniu $j$ nie wpływa na dzień $j+1$.

Mały P jest zainteresowany sumą niezadowolenia wszystkich osób, dlatego prosi Cię o obliczenie tej sumy dla każdego z $q$ dni.

Wejście

Pierwsza linia zawiera cztery liczby całkowite dodatnie $n, m, q, T$, oznaczające odpowiednio liczbę osób, liczbę stanowisk w łaźni, liczbę zapytań oraz stały czas trwania kąpieli.

W kolejnej linii znajduje się $n$ liczb całkowitych dodatnich, gdzie $i$-ta liczba $t_i$ oznacza czas przybycia $i$-tej osoby. Gwarantuje się, że $\forall i\in [1,n), t_i\le t_{i+1}$.

W kolejnych $q$ liniach znajdują się dwie liczby całkowite $x_j, t'_j$, oznaczające, że czas przybycia $x_j$-tej osoby w danym dniu (i tylko w tym dniu) zmienia się na $t'_j$.

Wyjście

Dla każdego z $q$ dni wypisz w osobnej linii jedną liczbę całkowitą oznaczającą sumę niezadowolenia wszystkich osób w tym dniu.

Przykład 1

Wejście 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

Wyjście 1

24
15
21
18
18

Przykład 2

Wejście 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

Wyjście 2

137
138
145
147
137
127
145
122
144
136

Ograniczenia

Dla wszystkich danych wejściowych: $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$.