Ferma

În preajma Crăciunului, pentru transportul celor $N$ porci de la ferma proprie la piață pentru vânzare, un gospodar are la dispoziție un singur mijloc de transport — o remorcă. Această remorcă poate transporta doar o greutate maximă $G$, număr natural. Gospodarul știe greutatea $g_i$ a fiecărui porc $i$ ($1 \leq i \leq N$), număr natural.

Cerință

Să se realizeze o repartizare a porcilor în $3$ grupuri astfel încât mijlocul de transport să poată realiza trei drumuri până la piață, iar diferența de greutate dintre cele $3$ transporturi să fie minimă.

Date de intrare

Fișierul de intrare ferma.in conține pe prima linie trei valori $C$, $N$, $G$, separate prin câte un spațiu, reprezentând cerința $C$ ($1$, $2$ sau $3$), numărul de porci și greutatea maximă permisă în remorcă. Următoarea linie conține $N$ valori naturale nenule separate prin câte un spațiu, $g_1, g_2, \dots, g_N$, reprezentând greutățile celor $N$ porci.

Date de ieșire

Dacă cerința este 1, fișierul de ieșire ferma.out va conține pe prima linie $3$ numere naturale separate prin câte un spațiu, reprezentând sumele greutăților din cele $3$ transporturi, scrise în ordine crescătoare.

Dacă cerința este 2, fișierul de ieșire va conține pe prima linie $N$ valori din mulțimea $\{1, 2, 3\}$, indicând transportul din care face parte fiecare porc; în cazul în care există mai multe soluții se va afișa soluția minimă din punct de vedere lexicografic.

Dacă cerința este 3, fișierul de ieșire va conține pe prima linie un sigur număr natural reprezentând diferența de greutate dintre cele $3$ transporturi.

Restricții și precizări

• $10 \leq N \leq 15$
• $10 \leq G \leq 40 \ 000$
• $1 \leq g_i \leq 10 \ 000$, pentru $1 \leq i \leq N$
• Pentru toate testele există soluție.

Exemplul 1

ferma.in

1 10 238
106 58 73 48 64 64 61 77 62 98

ferma.out

237 237 237

Explicație

Suma greutăților este $237$ în fiecare transport.

Exemplul 2

ferma.in

2 10 238
106 58 73 48 64 64 61 77 62 98

ferma.out

1 1 1 2 2 2 2 3 3 3

Explicație

Primii $3$ porci în transportul $1$, următorii $4$ porci în transportul $2$, ultimii $3$ porci în transportul $3$.

Alte soluții corecte:

• $2, 2, 2, 1, 1, 1, 1, 3, 3, 3$;
• $3, 3, 3, 1, 1, 1, 1, 2, 2, 2$;
• etc.

Exemplul 3

ferma.in

3 10 238
106 58 73 48 64 64 61 77 62 98

ferma.out

0

Explicație

Diferența este $0$.

Exemplul 4

ferma.in

1 7 33
9 1 8 2 7 3 4

ferma.out

11 11 12

Explicație

Transporturile $1$ și $2$ au fiecare greutatea $11$, iar transportul $3$ are greutatea $12$.

Exemplul 5

ferma.in

2 7 33
9 1 8 2 7 3 4

ferma.out

1 1 2 1 3 2 3

Explicație

O altă soluție corectă este $3, 3, 2, 3, 1, 2, 1$, dar nu este minimă lexicografic.

Exemplul 6

ferma.in

3 7 33
9 1 8 2 7 3 4

ferma.out

1

Explicație

Cea mai mare diferență între cele $3$ transporturi este $1$.