Winnie and Yoyo are having lots of spring fun with the flora and fauna in April. After fooling each other on 1st April, they decided to have a picnic at the Heung Shing Country Park.

Before going on the picnic, they have to prepare their food. Winnie loves walnuts while Yoyo loves yoghurt. They decided to make walnut yoghurt together!

There are $N$ walnuts, and the $i^{th}$ one has a tastiness $W_i$.

Yoyo first adds yoghurt to the walnuts for $Q$ times. The $j^{th}$ yoghurt has a tastiness of $Y_j$. After adding the $j^{th}$ yoghurt, $Y_j$ is added to every $W_i$ and this change in tastiness of walnuts will be accumulated.

Then, Winnie can perform the following operations any number of times: choose $K$ of the walnuts and merge them into a bigger walnut. The bigger walnut has a tastiness of the sum of the merged walnuts. Note that the operation can be applied if and only if there are at least $K$ elements left.

The overall tastiness of a walnut yoghurt is defined as the maximum tastiness among all walnuts. For every $Q$ times that a new yoghurt is added to the walnuts, find out the maximum overall tastiness of the walnut yoghurt if Winnie performs the walnut merging operations optimally. Find this value for the walnuts without adding any yoghurt too.

Input

The first line contains three integers $N$, $K$ and $Q$.
The next line contains $N$ integers, $W_1, W_2, ... , W_N$.
The next $Q$ lines each contains an integer, the one on the $j^{th}$ line is $Y_j$.

Output

Output $Q+1$ lines.
On the first line, find the maximum overall tastiness of the walnut yoghurt if Winnie performs the walnut merging operations optimally, for the walnuts without adding any yoghurt.
On the next $Q$ lines, output that value after the $j^{th}$ yoghurt is being added on the $j^{th}$ line.

Subtasks

For all cases,
$2 \le K \le N \le 10^5$
$1 \le Q \le 10^5$
$1 \le |W_i| \le 10^9 $
$1 \le |Y_i| \le 10^{10}$
It is guaranteed that at any time, for any subset $S$ in $W$, (sum of $S$) $\le 10^{17}$.

Subtask 1 (14 pts): $K = 2, Q = 0, N = 2$
Subtask 2 (14 pts): $K = 2, Q = 0$
Subtask 3 (15 pts): $K = 3, Q = 0, W_i \ge 0$
Subtask 4 (16 pts): $K = 2$
Subtask 5 (17 pts): $N,Q \le 1000$
Subtask 6 (24 pts): No additional constraints

walnut and yoghurts from: https://www.veryicon.com/icons/food--drinks/nut-snacks/walnut-15.html and https://stock.adobe.com/search?k=yogurt+with+spoon