Anul acesta școala Algocoin a organizat un concurs la care au participat N elevi. Pentru fiecare elev cunoaștem punctajul obținut la concurs. Directorul școlii a decis să-i recompenseze pe elevi prin acordarea unui număr de monede virtuale care pot fi folosite pentru a achiziționa produse de la magazinul școlii. Pentru a acorda monedele, directorul a ordonat elevii crescător după punctaj și i-a numerotat de la 1 la N. Apoi a asociat fiecărui elev monedele, astfel:

• elevul cu cel mai mic punctaj (elevul cu numărul de ordine 1) primeste punctajul său înmulțit cu 1 monede.
• dacă elevul cu numărul de ordine i are același punctaj cu elevul cu numărul de ordine i-1, atunci va primi același număr de monede ca elevul cu numărul de ordine i-1. În caz contrar, va primi punctajul său înmulțit cu i monede.

Magazinul virtual al școlii are o politică specială care promovează prietenia, astfel:

• pentru fiecare multiplu al unui număr specificat K există în magazin cel puțin un produs cu acel preț (da! magazinul virtual al școlii are o infinitate de produse);
• pentru a cumpăra un produs, un elev trebuie să-și găsească un prieten care să accepte ca ei să pună împreună monedele primite, iar suma totală deținută să fie egală cu prețul produsului cumpărat.

Cerința

Cunoscând numărul de elevi N , valorile K și P, precum și punctajul obținut de fiecare elev la concurs, scrieți un program care să rezolve următoarele cerințe:
1. afișează, în ordine crescătoare, numărul de monede primite de fiecare elev;
2. determină numărul total de perechi de elevi care s-ar putea forma pentru a putea cumpăra un produs din magazin;
3. determină prețul X (multiplu de K) al celui mai scump produs pentru care există cel puțin P perechi distincte de elevi, astfel încât orice elev să poată apărea în cel mult o pereche, iar suma monedelor celor doi elevi din fiecare pereche să fie strict mai mare decât X.

Date de intrare

Fișierul de intrare algocoin.in conține pe prima linie numărul natural C, reprezentând cerința care trebuie rezolvată (1, 2 sau 3). Pe a doua linie se află numerele naturale N K P, cu semnificația din enunț. Pe a treia linie se află N numere naturale reprezentând punctajele obținute de cei N elevi. Valorile scrise pe aceea și linie sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire algocoin.out va conține o singură linie pe care se află:

• dacă C = 1: N numere naturale, separate prin câte un spațiu, reprezentând numărul de monede primite de fiecare elev, în ordine crescătoare;
• dacă C= 2 sau C = 3: un număr natural reprezentând răspunsul la cerința C.

Restricții și precizări

• 2 ≤ N ≤ 200.000
• 1 ≤ punctajul oricărui elev ≤ 1.000.000
• 1 ≤ K ≤ 1000
• 1 ≤ P ≤ N/2
• Pentru 30 de puncte, C = 1
• Pentru 30 de puncte, C = 2, 10 ≤ N ≤ 1000
• Pentru 19 puncte, C = 2, fără restricții suplimentare
• Pentru 9 puncte, C = 3, 10 ≤ N ≤ 1000
• Pentru 12 puncte, C = 3, fără restricții suplimentare

Exemplul 1

algocoin.in

1
7 1 1
6 5 6 7 8 8 3

algocoin.out

3 10 18 18 35 48 48

Explicație

Punctajele în ordine crescătoare sunt: 3 5 6 6 7 8 8. Sumele primite vor fi 1·3, 2·5, 3·6, 3·6, 5·7, 6·8, 6·8.

Exemplul 2

algocoin.in

2
7 9 1
6 5 6 7 8 8 1

algocoin.out

3

Explicație

Trebuie să determinăm numărul de perechi de elevi care se pot forma pentru care suma monedelor primite de cei doi să fie multiplu de 9. Sumele primite de elevi sunt: 1 10 18 18 35 48 48.

Se pot forma trei perechi:

• cei doi elevi care au câte 18 monede;
• elevul care are 10 monede și cel care are 35 de monede;
• elevul care are o monedă și cel care are 35 de monede.

Exemplul 3

algocoin.in

3
7 5 2
6 5 6 7 8 8 3

algocoin.out

65

Explicație

Cel mai mare multiplu al lui K = 5 pentru care putem obține cel puțin P = 2 perechi distincte de elevi astfel încât suma monedelor celor doi elevi din fiecare pereche să fie strict mai mare decât X, iar fiecare elev să poată apărea în cel mult o pereche este 65.

Sumele primite de elevi sunt: 3 10 18 18 35 48 48. O posibilitate de a forma două perechi conform condițiilor din enunt, este de a alege un elev cu suma 18 si un elev cu suma 48, respectiv celălalt elev cu suma 48 si elevul cu suma 35.