secvp

Se consideră un şir cu $N$ numere naturale $a_1, a_2, \dots, a_N$. Asupra unui element $a_i$ din şir se pot efectua operaţii de incrementare (adunare cu $1: a_i = a_i + 1$) sau decrementare (scădere cu $1: a_i = a_i - 1$). Fiecare element din şir poate fi incrementat sau decrementat de oricâte ori.

Cerința

Dat fiind șirul celor $N$ numere naturale, să se determine:

1. numărul total minim de operaţii necesare pentru a transforma toate numerele din şir în numere prime;
2. numărul minim de operații (incrementări şi decrementări) ce trebuie să fie efectuate asupra elementelor şirului astfel încât să existe o secvență de lungime $K$ formată numai din numere prime.

Date de intrare

Fișierul de intrare secvp.in conține pe prima linie numerele naturale $N$ şi $K$, iar pe următoarea linie $N$ numere naturale. Numerele scrise pe aceeași linie sunt separate prin spații.

Date de ieșire

Fișierul de ieșire secvp.out conţine pe prima linie un număr natural $T$, reprezentând numărul total minim de operaţii necesare pentru a transforma toate numerele din şir în numere prime. Pe a doua linie vor fi scrise două numere naturale separate prin spaţiu $minK nrsK$, unde $minK$ reprezintă numărul minim de operaţii ce trebuie să fie efectuate asupra elementelor şirului astfel încât să existe o secvenţă de lungime $K$ formată numai din numere prime, iar $nrsK$ reprezintă numărul de secvenţe de lungime $K$ care se pot obţine cu acelaşi număr $minK$ de operaţii de incrementare/decrementare.

Restricții și precizări

• $2 \leq K \leq N \leq 100 \ 000$
• $0 \leq a_i \leq 1 \ 000 \ 000$, pentru $1 \leq i \leq N$
• O secvență din șir este formată din elemente aflate pe poziţii consecutive în şirul dat.
• $1$ nu este număr prim.
• Pentru determinarea corectă a valorii $T$ se acordă $30\%$ din punctajul pe test. Pentru determinarea corectă a valorilor $T$ şi $minK$ se acordă $70\%$ din punctajul pe test. Punctajul integral se acordă pentru determinarea corectă a tuturor celor $3$ valori.

Exemplul 1

secvp.in

7 3
15 3 8 26 22 10 14

secvp.out

9
3 2

Explicație

Pentru a transforma $15$ în număr prim sunt necesare $2$ incrementări.
Pentru a transforma $3$ în număr prim sunt necesare $0$ operaţii.
Pentru a transforma $8$ în număr prim e necesară $1$ decrementare.
Pentru a transforma $26$ în număr prim sunt necesare $3$ decrementări.
Pentru a transforma $22$ în număr prim e necesară $1$ incrementare.
Pentru a transforma $10$ în număr prim e necesară $1$ incrementare.
Pentru a transforma $14$ în număr prim e necesară $1$ decrementare.
Numărul total de operaţii necesare este $9$.
Numărul minim de operaţii necesare pentru a obţine o secvenţă de lungime $K$ este $3$. Cele două secvenţe de lungime $K$ ce necesită $3$ operaţii sunt $a_1, a_2, a_3$ şi $a_5, a_6, a_7$.