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は非常に厳格な人物であるため、この平均値を既約分数として出力する必要があります。

入力

1行目に3つの整数 $n, k, m$ が与えられます。これらはそれぞれ探査車の可動範囲、探査車の最短長、および磁場強度の変更回数を表します。

続く1行に $n$ 個の整数が与えられ、第 $i$ 番目の $a_i$ はその区間で磁場が提供する電力量を表します。

続く $m$ 行には、それぞれ2つの整数 $p, x$ が与えられ、位置 $p$ における磁場提供電力量を $x$ に変更することを表します。

出力

合計 $m+1$ 行を出力してください。1行目には初期状態での最適な平均電力量を出力し、続く第 $i$ 行には $i-1$ 回目の更新後の最適な平均電力量を出力してください。

具体的な出力形式は、有理数を既約分数 $\frac xy$ の形式で表し、$\mathbf{y=1}$ の場合は $\mathbf{x}$ を出力し、それ以外の場合は $\mathbf{x/y}$ を出力してください。

入出力例

入力 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$ となります。

1回目の更新後、データは $(2, 6, 2, 6, 6)$ となり、引き続き区間 $[1, 5]$ を選択します。

2回目の更新後、データは $(6, 6, 2, 6, 6)$ となり、区間 $[0, 5]$ を選択します。

入力 2

配布ファイルを参照してください。

制約

すべてのデータにおいて、$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$ を満たします。