== include(page="template/taskheader" task_id="prajituri") ==
Poveste și cerință...
Moș Crăciun a găsit sub brad $n$ borcane cu prăjituri, numerotate de la $1$ la $n$. Borcanul $i$ conține $a[~i~]$ prăjituri.
Moș Crăciun vrea să mănînce prăjituri, dar are două reguli ciudate:
* Din fiecare borcan, Moșul mănîncă fie toate prăjiturile, fie niciuna.
* Moșul dorește să mănînce un număr maxim de prăjituri modulo $m$.
Aflați numărul maxim de prăjituri pe care Moșul le poate mînca modulo $m$ și ce borcane trebuie să mănînce.
h2. Date de intrare
Fișierul de intrare $prajituri.in$ ...
Fișierul de intrare $prajituri.in$ conține pe prima linie numerele $n$ și $m$. Pe următoarea linie apar valorile $a[~1~], a[~2~], ..., a[~n~]$.
h2. Date de ieșire
În fișierul de ieșire $prajituri.out$ ...
În fișierul de ieșire $prajituri.out$ afișați pe prima linie numărul maxim de prăjituri modulo $m$ pe care le poate mînca Moșul. Pe a doua linie afișați un șir de $0$ și $1$, fără spații, în care al [$i$]-lea caracter este $1$ dacă Moșul mănîncă prăjiturile din borcanul $i$ sau $0$ în caz contrar.
Dacă există mai multe soluții, afișați-o pe oricare.
h2. Restricții
* $... ≤ ... ≤ ...$
• $2 ≤ n ≤ 40$
• $1 ≤ m ≤ 10.000.000$
• $1 ≤ a[~i~] < m$ pentru $1 ≤ i ≤ n$
• Testele *nu* sînt grupate.
table{width: inherit}.
|_. subtask |_. puncte |_. restricții |
| 1 | 52 | $n ≤ 24$ |
| 2 | 36 | $n ≤ 37$ |
| 3 | 12 | Fără restricții suplimentare. |
h2. Exemplu
table(example).
table(example).
|_. prajituri.in |_. prajituri.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5 50
38 37 44 6 22
| 47
11001
|
h3. Explicație
...
Moș Crăciun mănîncă borcanele 1, 2 și 5, care au 97 de prăjituri în total (adică 47 modulo 50).
== include(page="template/taskfooter" task_id="prajituri") ==
