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ța

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 ≤ N ≤ 500 000
• 1 ≤ K ≤ 2 000 000 000
• 1 ≤ M ≤ 500 000
• 0 ≤ numărul de ghinde de pe o ramură ≤ 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

pre.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