Vnoroc

Pentru avea succes la Olimpiada de Jocuri pe Internet (OJI), Vasilică a cumpărat de la Baba Yaga un talisman norocos. Talismanul norocos este un șir care îndeplineşte următoarele două condiţii:

1. toate elementele șirului sunt cifre mai mici sau egale cu magicul $7$;
2. oricare două elemente aflate pe poziții consecutive în șir au cel puţin un divizor comun strict mai mare decât $1$.

De exemplu, $(7, 7, 7)$, $(6, 0, 0, 4, 0)$ și $(2, 6, 3)$ sunt talismane norocoase, dar $(1, 2, 3)$, $(2, 4, 7)$ și $(5, 6, 5)$ nu sunt.

Cel mai mare rival al lui Vasilică, pe nume Acilisav, a aflat de planul lui de a folosi magie pentru a câștiga competiția de jocuri şi s-a furișat în noaptea de dinainte de OJI în casa lui Vasilică și i-a modificat talismanul, adăugând cifre mai mici sau egale cu $7$.

Vasilică vrea să elimine cifre din șir, astfel încât șirul să redevină un talisman norocos.

Cerință

Cunoscând șirul $V$ modificat de Acilisav:

1. determinaţi numărul minim de cifre care trebuie să fie eliminate din șirul $V$, astfel încât acesta să devină talisman norocos;
2. determinaţi talismanul norocos minim lexicografic, care se obţine eliminând din șirul $V$ un număr minim de cifre.

Date de intrare

Fişierul de intrare vnoroc.in conţine pe prima linie numerele naturale $C$ și $N$, reprezentând cerința care trebuie să fie rezolvată ($1$ sau $2$), respectiv numărul de elemente din șirul $V$. Pe a doua linie se află $N$ cifre separate prin câte un spațiu, reprezentând elementele șirului $V$.

Date de ieșire

Fişierul de ieşire vnoroc.out conţine o singură linie, pe care este scris:

1. dacă $C = 1$, un număr natural $nr$, reprezentând numărul minim determinat pentru cerința $1$;
2. dacă $C = 2$, $(N-nr)$ cifre separate prin câte un spaţiu, reprezentând talismanul norocos minim lexicografic, determinat pentru cerința $2$.

Restricții și precizări

• $2 \leq N \leq 10^{6}$
• Cifrele din șirul $V$ sunt mai mici sau egale cu 7.
• Spunem că șirul $a_1$, $a_2$, $\dots a_N$ este mai mic strict din punctul de vedere lexicografic decât șirul $b_1$, $b_2$, $\dots b_N$ dacă există $k$ ($1 \leq k \leq N$), astfel încât $a_i=b_i$, pentru orice $1 \leq i<k$ şi $a_k<b_k$.

Exemplul 1

vnoroc.in

1 5
4 4 3 6 2

vnoroc.out

1

Explicație

Pentru ca șirul să devină norocos, este suficient să eliminăm cifra $3$.

Exemplul 2

vnoroc.in

2 5
4 4 3 6 2

vnoroc.out

4 4 6 2

Explicație

Singura soluţie care se poate obţine eliminând un număr minim de cifre ($1$) este $4$ $4$ $6$ $2$.

Exemplul 3

vnoroc.in

2 6
5 7 5 7 5 7

vnoroc.out

5 5 5

Explicație

Numărul minim de cifre care trebuie să fie eliminate este $3$. Se pot obţine două talismane norocoase prin eliminarea a câte $3$ cifre: $(5, 5, 5)$ și $(7, 7, 7)$. Se afișează talismanul norocos minim lexicografic $5$ $5$ $5$.

Exemplul 4

vnoroc.in

2 9
2 3 5 3 7 0 0 5 1

vnoroc.out

3 3 0 0 5

Explicație

Numărul minim de cifre care trebuie să fie eliminate este $4$. Se poate obţine un singur talisman norocos $(3, 3, 0, 0, 5)$ prin eliminarea a $4$ cifre.