В 2019 году исследовательская группа EI прибыла в Антарктиду для проведения научных изысканий. В отличие от стационарных станций, они используют новый тип исследовательского вездехода, энергия для которого вырабатывается за счет магнитного поля Антарктиды. Вездеход может растягиваться на любую длину, но его минимальная длина составляет $k$ (далее все единицы измерения по умолчанию — метры). Область перемещения вездехода можно представить как движение по числовой прямой: передняя часть вездехода не может быть меньше $0$, а задняя — больше $n$. Согласно измерениям, магнитное поле на отрезке $[i-1, i]$ обеспечивает количество энергии $a_i$.

Поскольку чем длиннее вездеход, тем больше энергии требуется для внутренних систем, EI интересует среднее количество энергии, вырабатываемое на единицу длины вездехода, то есть общая выработанная энергия, деленная на текущую длину вездехода. Для упрощения задачи положения передней и задней частей, а также длина вездехода должны быть целыми числами. Если вездеход находится на отрезке $[l-1, r]$ ($r - l + 1 \ge k$), то средняя энергия равна

$$ \frac1{r-l+1}\sum_{i=l}^r a_i $$

EI хочет, чтобы вы оптимально спланировали положение вездехода так, чтобы максимизировать среднюю энергию и обеспечить успешное проведение экспериментов.

Однако в течение $m + 1$ дня, из-за геологических процессов, каждый день обнаруживается, что интенсивность магнитного поля на некотором участке меняется, то есть значение одного из $a_i$ обновляется.

EI занят планированием экспериментов, поэтому просит вас помочь вычислять оптимальную среднюю энергию на каждый день. EI — очень педантичный человек, поэтому вам нужно вывести это среднее значение в виде рационального числа.

Входные данные

Первая строка содержит три целых числа $n, k, m$, обозначающих диапазон перемещения вездехода, минимальную длину вездехода и общее количество изменений интенсивности магнитного поля соответственно.

Следующая строка содержит $n$ целых чисел, где $i$-е число $a_i$ обозначает количество энергии, обеспечиваемое магнитным полем на данном участке.

Далее следуют $m$ строк, каждая из которых содержит два целых числа $p, x$, означающих, что значение энергии в точке $p$ изменено на $x$.

Выходные данные

Всего необходимо вывести $m+1$ строку. В первой строке выведите начальную оптимальную среднюю энергию, а в каждой последующей $i$-й строке — оптимальную среднюю энергию после $i-1$ обновлений.

Конкретные требования к выводу: пусть искомое рациональное число представлено в виде несократимой дроби $\frac xy$. Если $\mathbf{y=1}$, выведите $\mathbf{x}$, в противном случае выведите $\mathbf{x/y}$.

Примеры

Пример 1

Входные данные 1

5 3 2
2 8 2 6 6
2 6
1 6

Выходные данные 1

11/2
5
26/5

Примечание 1

Изначально выбираем отрезок $[1, 5]$, тогда средняя энергия равна $\frac14(a_2+a_3+a_4+a_5)=\frac{11}2$.

После первого изменения данные становятся $(2, 6, 2, 6, 6)$, по-прежнему выбираем отрезок $[1, 5]$.

После второго изменения данные становятся $(6, 6, 2, 6, 6)$, выбираем отрезок $[0, 5]$.

Пример 2

См. прилагаемые файлы.

Ограничения

Для $100\%$ данных гарантируется $1 \le n\le 10^5, 1\le k \le \min(n, 10), 0 \le m \le 10^5, 1\le a_i, x\le 10^4, 1\le p \le n$.