W 2019 roku zespół badawczy EI przybył na Antarktydę w celu przeprowadzenia badań naukowych. W przeciwieństwie do stacji badawczych budowanych na powierzchni, korzystają oni z nowego typu pojazdu badawczego, którego energia jest zasilana przez pole magnetyczne Antarktydy. Pojazd ten może zmieniać swoją długość w dowolny sposób, jednak jego minimalna długość wynosi $k$ (wszystkie jednostki długości podano w metrach). Zakres ruchu pojazdu można rozpatrywać jako poruszanie się po osi liczbowej, przy czym przód pojazdu nie może znajdować się w punkcie mniejszym niż $0$, a tył nie może przekraczać $n$. Pomiary wykazały, że pole magnetyczne w przedziale $[i-1, i]$ dostarcza energię o wartości $a_i$.

Ponieważ im dłuższy jest pojazd, tym więcej energii zużywają urządzenia wewnętrzne, EI interesuje się średnią ilością energii dostarczanej na jednostkę długości pojazdu, czyli całkowitą ilością wygenerowanej energii podzieloną przez aktualną długość pojazdu. Dla uproszczenia problemu przyjmuje się, że położenie przodu, położenie tyłu oraz długość pojazdu muszą być liczbami całkowitymi. Jeśli pojazd znajduje się w przedziale $[l-1, r]$ (gdzie $r - l + 1 \ge k$), średnia ilość energii wynosi:

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

EI prosi o zaplanowanie położenia pojazdu w taki sposób, aby zmaksymalizować średnią ilość energii, co zapewni powodzenie eksperymentu.

Jednak w ciągu $m + 1$ dni pobytu, ze względu na procesy geologiczne, każdego kolejnego dnia zmienia się natężenie pola magnetycznego w pewnym odcinku, co oznacza, że jedna z wartości $a_i$ ulega zmianie.

EI jest zajęty planowaniem eksperymentów, więc prosi o pomoc w obliczeniu optymalnej średniej energii każdego dnia. EI jest bardzo skrupulatny, dlatego wynik należy podać w postaci ułamka nieskracalnego.

Wejście

Pierwsza linia zawiera trzy liczby całkowite $n, k, m$, oznaczające zakres ruchu pojazdu, minimalną długość pojazdu oraz łączną liczbę zmian natężenia pola magnetycznego.

Kolejna linia zawiera $n$ liczb całkowitych, gdzie $i$-ta liczba $a_i$ oznacza energię dostarczaną przez pole magnetyczne w danym odcinku.

Następnie $m$ linii, z których każda zawiera dwie liczby całkowite $p, x$, oznaczające zmianę wartości energii w punkcie $p$ na $x$.

Wyjście

Należy wypisać łącznie $m+1$ linii. Pierwsza linia zawiera początkową optymalną średnią energię, a każda kolejna linia $i$ zawiera optymalną średnią energię po $i-1$ aktualizacjach.

Szczegółowe wymagania dotyczące formatu wyjścia: jeśli wynik jest ułamkiem nieskracalnym $\frac xy$, jeśli $\mathbf{y=1}$, należy wypisać $\mathbf{x}$, w przeciwnym razie należy wypisać $\mathbf{x/y}$.

Przykład

Przykład 1

Wejście 1

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

Wyjście 1

11/2
5
26/5

Uwagi 1

Początkowo wybieramy przedział $[1, 5]$, więc średnia energia wynosi $\frac14(a_2+a_3+a_4+a_5)=\frac{11}2$.

Po pierwszej zmianie dane stają się $(2, 6, 2, 6, 6)$, nadal wybieramy przedział $[1, 5]$.

Po drugiej zmianie dane stają się $(6, 6, 2, 6, 6)$, wybieramy przedział $[0, 5]$.

Ograniczenia

Dla $100\%$ danych: $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$.