In 2019, the EI polar expedition team arrived in Antarctica for scientific research. Unlike research stations built on the ground, they use a new type of research vehicle whose energy is supplied by generating electricity from the Antarctic magnetic field. This vehicle can extend or retract to any length, but its minimum length is $k$ (all units are in meters by default). The vehicle's range of motion can be viewed as movement along a number line, where the front of the vehicle cannot be less than $0$ and the rear cannot be greater than $n$. Measurements show that the magnetic field in the interval $[i-1, i]$ provides an amount of electricity equal to $a_i$.

Since the longer the vehicle extends, the more electricity the internal facilities require, EI is only concerned with the average electricity supplied per segment of the vehicle, which is the total generated electricity divided by the current length of the vehicle. To simplify the problem, the positions of the front and rear of the vehicle, as well as the vehicle length, must be integers. If the vehicle is parked at the position $[l-1, r]$ (where $r - l + 1 \ge k$), the average electricity is equal to:

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

EI wants you to reasonably plan the vehicle's position to maximize the average electricity, ensuring his experiments can proceed smoothly.

However, during the $m + 1$ days you stay there, due to geological activity, the magnetic field strength in a certain segment will change after each new day, meaning one $a_i$ will be modified.

EI is busy planning experiments, so please help him calculate the optimal electricity for each day. EI is a very rigorous person, so you need to output this average as a rational number.

Input

The first line contains three integers $n, k, m$, representing the range of motion of the research vehicle, the minimum length of the vehicle, and the total number of magnetic field strength changes, respectively.

The next line contains $n$ integers, where the $i$-th integer $a_i$ represents the electricity provided by the magnetic field in that segment.

The next $m$ lines each contain two integers $p, x$, representing that the magnetic field electricity recorded at position $p$ is modified to $x$.

Output

Output $m+1$ lines in total. The first line outputs the initial optimal average electricity, and each subsequent $i$-th line outputs the optimal average electricity after the $(i-1)$-th update.

The specific output requirement is: let the rational number be in the simplest fraction form $\frac xy$. If $\mathbf{y=1}$, please output $\mathbf{x}$; otherwise, output $\mathbf{x/y}$.

Examples

Input 1

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

Output 1

11/2
5
26/5

Note 1

Initially, selecting the interval $[1, 5]$, the average electricity is $\frac14(a_2+a_3+a_4+a_5)=\frac{11}2$.

After the first modification, the data becomes $(2, 6, 2, 6, 6)$, and the interval $[1, 5]$ is still selected.

After the second modification, the data becomes $(6, 6, 2, 6, 6)$, and the interval $[0, 5]$ is selected.

Input 2

See the provided file.

Subtasks

For $100\%$ of the data, it is guaranteed that $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$.