Маленький P любит изучать различные жизненные задачи, и недавно он всерьез занялся вопросом посещения душа. В общежитии, где живет Маленький P, в душевой на этаже есть $m$ мест (то есть $m$ человек могут мыться одновременно). Каждый день $n$ человек хотят принять душ, время прихода каждого человека — $t_i$, а время, затрачиваемое на мытье, фиксировано и равно $T$.

Если $i$-й человек приходит в душ в момент времени $t_i$ и свободных мест нет, он вынужден ждать, пока кто-нибудь освободит место. Как только место освобождается, он немедленно начинает мыться.

Пусть $s_i$ — время, когда $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$.