alipiri

Spunem că numărul natural nenul $n_1$ se poate alipi pe $K$ biţi cu numărul natural nenul $n_2$ dacă reprezentările lor binare au fiecare cel puţin $K$ biţi (primul bit fiind $1$), iar ultimii $K$ biţi ai numărului $n_1$ coincid cu primii $K$ biţi ai numărului $n_2$. După alipire rezultă un alt număr, format din concatenarea lui $n_1$ cu $n_2$, dar în care secvenţa comună de $K$ biţi apare o singură dată şi în ea fiecare bit este înlocuit cu complementarul său ($0$ devine $1$ şi invers).

Exemplu: Numărul $78$ = $1001110_2$ se poate alipi pe $3$ biţi cu $25$ = $11001_2$ şi rezultă numărul $100100101_2 = 293$.

Numerele $nr_1$, $nr_2$, $\dots$, $nr_M$ formează o listă de alipiri pe $K$ biţi, de lungimea $M \geq 1$, cu finalul $P$, dacă $nr_1$ se alipeşte pe $K$ biţi cu $nr_2$, rezultatul se alipeşte pe $K$ biţi cu $nr_3$, $\dots$, rezultatul se alipeşte pe $K$ biţi cu $nr_M$, iar rezultatul final este numărul $P$. Notă: Dacă $M = 1$, atunci trebuie să avem $nr_1$ = $P$.

Cerinţă

Pentru un şir dat de numere naturale nenule şi valorile naturale nenule $K$ şi $P$, se cere:

$a)$ să se determine lungimea maximă a unei liste de alipiri pe $K$ biţi, formată cu elemente din şirul dat, nu neaparat în ordinea din acest şir;
$b)$ să se verifice dacă se poate obţine, cu numere din şirul dat, o listă de alipiri pe $K$ biţi cu finalul $P$; în caz afirmativ să se precizeze o listă de lungime minimă de alipiri pe $K$ biţi cu finalul $P$.

Date de intrare

Fişier de intrare: alipiri.in

• Linia $1$: $N \ K \ P$ - trei numere naturale nenule, separate prin câte un spaţiu, reprezentând numărul $N$ al numerelor date, lungimea $K$ a secvenţelor comune din alipiri, respectiv valoarea $P$ a numărului care trebuie obţinut prin alipiri;
• Linia $2$: $nr_1 \ nr_2 \ \dots \ nr_N$ - $N$ numere naturale nenule, separate prin câte un spaţiu, reprezentând şirul dat.

Date de ieșire

Fişier de ieşire: alipiri.out

• Linia $1$: $M$ - număr natural nenul, reprezentând rezultatul de la cerinţa $a)$;
• Linia $2$: mesaj - dacă cerinţa $b)$ poate fi satisfăcută, pe această linie se va scrie DA, în caz contrar se va scrie NU;
• Linia $3$: $nr_1 \ nr_2 \ \dots$ - dacă pe linia $a)$ aţi scris 'DA', pe această linie se va scrie o listă de alipiri (pe $K$ biţi) de lungime minimă cu finalul $P$; numerele din listă se vor separa prin câte un spaţiu.

Restricții și precizări

• $1 \leq K \leq 8$;
• $1 \leq N \leq 9$;
• $1 \leq P \leq 2 \cdot 10^9$;
• dacă cerinţa $b)$ este satisfăcută de mai multe liste (de lungime minimă), în fişier se va scrie una singură.
• pentru ambele cerinţe fiecare număr din şirul de intrare poate apărea cel mult o dată în listele de alipiri considerate.
• Notă. Se acordă punctaje parţiale: $a) \ 40\%; \ b) \ 60\%$

Exemplu

alipiri.in

4 3 291    	    
14 59 36 31

alipiri.out

4
DA
59 31 14