familie

Un grup de geologi a descoperit $n$ fosile, notate prin numerele $1, 2, \dots, n$ şi a estimat vârsta geologică a fiecărei fosile printr-un număr natural, obţinând astfel un şir de $n$ numere naturale, notate $v_1, v_2, \dots, v_n$, unde $v_1$ este vârsta primei fosile descoperite, $v_2$ este vârsta celei de-a doua fosile descoperite etc. A urmat clasificarea fosilelor în $k$-familii, în funcţie de vârstă. O $k$-familie este formată din vârstele fosilelor pentru care reprezentările în baza $2$ conţin exact $k$ zerouri, fosilele fiind selectate în ordinea descoperirii lor.
Din fosilele unei $k$-familii se formează ramuri ale $k$-familiei, astfel încât fiecare fosilă aparţine unei singure ramuri. O ramură a unei $k$-familii oarecare, notată $a_1, a_2, \dots, a_n$, reprezintă un subşir strict crescător al său, de forma $a_{j1}, a_{j2}, \dots, a_{jp}$, unde $1 \leq j_1 < j_2 < \dots < j_p \leq n$ şi $a_{j1} < a_{j2} < \dots < a_{jp}$, $j_{i+1} - j_i \geq 1$, $\forall 1 \leq i < n$. Geologii trebuie să determine $k$-familia obţinută din şirul vârstelor fosilelor, pentru o anumită valoare $k$ şi să stabilească ramurile $k$-familiei, utilizând toate fosilele ei.

Cerinţă

Realizaţi un program care afişează $k$-familia obţinută din şirul vârstelor fosilelor şi numărul cel mai mic de ramuri ce se pot obţine, utilizând toate fosilele $k$-familiei afişate.

Date de intrare

Fişierul de intrare familie.in conţine pe prima linie două numere naturale $n$ şi $k$, ce reprezintă numărul de fosile descoperite şi respectiv numărul de zerouri utilizat pentru $k$-familia determinată şi pe a doua linie conţine $n$ numere naturale $v_1, v_2, \dots, v_n$, separate prin câte un spaţiu, ce reprezintă şirul vârstelor celor $n$ fosile.

Date de ieşire

Fişierul de ieşire familie.out va conţine pe prima linie un şir de numere naturale, separate între ele printr-un spaţiu, ce reprezintă vârstele fosilelor din $k$-familia obţinută şi pe a doua linie un număr natural ce reprezintă numărul cel mai mic de ramuri ale $k$-familiei, obţinut prin utilizarea tuturor fosilelor $k$-familiei.

Restricţii şi precizări

• $0 < n < 3\ 000$
• $0 < k < 30$
• $10\ 000 < v_i < 2\ 000\ 000\ 000$, $\forall\ 1 \leq i \leq n$
• O ramură conţine una sau mai multe fosile

Exemplul 1

familie.in

8 9
11024 11136 12039 11072 12032 11136 11075 11040

familie.out

11024 11136 11072 12032 11136 11040
3

Explicație

K-familia conţine numerele $11024$, $11136$, $11072$, $12032$, $11136$, $11040$ (ce au câte $9$ zerouri în reprezentarea lor în baza $2$). $K$-familia este formată din $3$ ramuri, acestea pot fi alese astfel: prima ramură este $11024$, $11136$, $12032$; a doua ramură este $11072$, $11136$; a treia ramură este $11040$.