Alipiri

     Doua numere naturale nenule n1 si n2 se pot "alipi" pe K biti, daca īn reprezentarea lor binara au fiecare cel putin K biti (primul bit fiind 1), iar ultimii K biti ai numarului n1 coincid cu primii K biti ai numarului n2. Dupa alipire rezulta un alt numar, format din concatenarea lui n1 cu n2, dar īn care secventa comuna de K biti apare o singura data si īn ea fiecare bit este īnlocuit cu complementarul sau (0 devine 1 si invers).

     Exemplu: Numerele 78=10011102 si 25=110012 se pot alipi pe 3 biti si rezulta numarul 1001001012=293, numerele 78 si 25 fiind pierdute.

      Numerele nr1, nr2, ..., nrM formeaza o lista de alipiri pe K biti de lungimea M > 0, cu finalul P, daca nr1 se alipeste pe K biti cu nr2, rezultatul se alipeste pe K biti cu nr3, ... , rezultatul se alipeste pe K biti cu nrM, iar rezultatul final este numarul P.

Cerinta

     Pentru un sir dat de numere naturale nenule si valorile naturale nenule K si P, se cere:
a)      sa se determine lungimea maxima a unei liste de alipiri pe K biti, formata cu elemente din sirul dat, nu neaparat īn ordinea din acest sir; 
b)      sa se verifice daca se poate obtine, cu numere din sirul dat, o lista de alipiri pe K biti cu finalul P; īn caz afirmativ sa se precizeze o lista de lungime minima de alipiri pe K biti cu finalul P.

Date de intrare

Fisier de intrare: ALIPIRI.IN

Linia 1: N K P
· Trei numere naturale nenule, separate prin cāte un spatiu, reprezentānd numarul N al numerelor date, lungimea K a secventelor comune din alipiri, respectiv valoarea P a numarului care trebuie obtinut prin alipiri;

Linia 2: nr1 nr2 ... nrN
· N numere naturale nenule, separate prin cāte un spatiu, repre­zen­tānd sirul dat.

Date de iesire

Fisier de iesire: ALIPIRI.OUT

Linia 1: M
·       numar natural nenul, reprezentānd rezultatul de la cerinta a);

Linia 2: mesaj
·       daca cerinta b) poate fi satisfacuta, pe aceasta linie se va scrie 'DA', īn caz contrar se va scrie 'NU';

Linia 3: nr1 nr2 ...
·       daca pe linia 2 ati scris 'DA', pe aceasta linie se va scrie o lista de alipiri (pe K biti) de lungime minima cu finalul P; numerele din lista se vor separa prin cāte un spatiu.

Restrictii
·       0 < K < 16 , 0 < N < 31 , 0 < P < 2000000000 (doua miliarde).
·       daca cerinta b) este satisfacuta de mai multe liste (de lungime minima), īn fisier se va scrie una singura.
·       numerele din sirul dat sunt mai mici ca 32000;
·       pentru ambele cerinte fiecare numar din sirul de intrare poate aparea cel mult o data īn listele de alipiri considerate.

Exemplu

ALIPIRI.IN
4 3 291
14 59 36 31

ALIPIRI.AUT
4
DA
59 31 14

Nota. Se acorda punctaje partiale: a) 40%; b) 60%

Timp maxim de executare/test: 3 secunde