algocoin

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$) primește 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$ în magazin există 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ță

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 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 \le N \le 200 \ 000$;
• $1 \le$ punctajul oricărui elev $\le 10^6$;
• $1 \le K \le 1000$;
• $1 \le P \le N / 2$.

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 \cdot 3$, $2 \cdot 5$, $3 \cdot 6$, $3 \cdot 6$, $5 \cdot 7$, $6 \cdot 8$, $6 \cdot 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 enunț este de a alege un elev cu suma $18$ și un elev cu suma $48$, respectiv celălalt elev cu suma $48$ și elevul cu suma $35$.