ghinde

Scrat și Scratte sunt două veverițe devoratoare de ghinde. Ele trăiesc într-un stejar înalt și culeg ghinde din cele $N$ ramuri ale acestuia. Veverițele vor organiza un concurs: cine culege cele mai multe ghinde în $K$ ture. Într-o tură, fiecare veveriță se va deplasa de la vizuină până la o ramură a stejarului, de unde va culege cât mai multe ghinde, dar nu mai mult de $M$ ghinde, după care va reveni în vizuină. Veverițele vor efectua alternativ fiecare câte $K$ ture, prima care începe fiind Scratte.

Supărat că la concurs nu va începe primul, Scrat decide să se antreneze separat și să vadă câte ghinde ar culege în $K$ ture, dacă ar fi singur

Cerință

Să se realizeze un program care determină:

1. Câte ghinde culege Scrat în timpul antrenamentului;
2. Câte ghinde a cules fiecare veveriță pe durata concursului.

Date de intrare

Fișierul de intrare Pe prima linie a fișierului ghinde.in conţine pe prima linie un număr natural $C$. Pentru toate testele, $C$ poate lua numai valorile $1$ sau $2$. Pe a doua linie se găsesc numerele $N$, $M$ și $K$ reprezentând numărul de ramuri ale stejarului, numărul maxim de ghinde culese la o tură, respectiv numărul de ture. Pe următoarele $N$ linii se găsesc numărul de ghinde de pe fiecare ramură în parte.

Date de ieșire

Dacă valoarea lui $C$ este $1$, se va rezolva numai punctul $1$ din cerințe. În acest caz, fişierul de ieşire ghinde.out va conține numărul total de ghinde cules în timpul antrenamentului de Scrat.

Dacă valoarea lui $C$ este $2$, se va rezolva numai punctul $2$ din cerințe. În acest caz, fişierul de ieşire ghinde.out va conține pe aceeași linie două numere naturale, separate printr-un spațiu, reprezentând în ordine, numărul de ghinde culese de Scratte respectiv Scrat, pe durata concursului.

Restricții și precizări

• $1 \leq N ≤ 500 \ 000$
• $1 \leq K ≤ 2 \ 000 \ 000 \ 000$
• $1 \leq M ≤ 500 \ 000$
• $0 \leq$ numărul de ghinde de pe o ramură $\leq 500 \ 000$
• Pentru rezolvarea corectă a primei cerințe se obțin $20$ de puncte, iar pentru rezolvarea corectă a celei de a doua cerințe se obțin $80$ puncte

Exemplul 1

ghinde.in

1
3 10 3
13
19
4

ghinde.out

29

Explicație

Scart culege $10$ ghinde de pe prima ramura, apoi $10$ de pe a doua ramura și alte $9$ de pe a doua ramura, adică $10 + 10 + 9 = 29$

Exemplul 2

ghinde.in

2
4 10 3
13
19
4
7

ghinde.out

23 20

Explicație

Scratte: $10$ de pe ramura a doua;
Scrat: $10$ de pe ramura unu;
Scratte: $9$ de pe ramura doi;
Scrat: $7$ de pe ramura patru;
Scratte: $4$ de pe ramura trei;
Scrat: $3$ de pe ramura unu;
Scratte: $10+9+4=23$
Scrat: $10+7+3=20$