influent

Se dă un șir cu $n$ numere naturale aflate pe poziții de la $1$ la $n$.

Definim influența unui număr (notată de noi cu $k$) ca fiind egală cu numărul de factori care apar în scrierea sa ca produs de numere prime. De exemplu, influența numărului $24$ este $4$, pentru că $24 = 2 \cdot 2 \cdot 2 \cdot 3$. Când își manifestă influența, un număr din șir afectează elementul de pe poziția sa, elementele de pe cele cel mult $k$ poziții din stânga sa și elementele aflate pe cele cel mult $k$ poziții din dreapta sa. Toate aceste valori se măresc cu $k$.
Pentru fiecare poziție $p$ de la $1$ la $n$, numărul aflat în șirul inițial pe poziția $p$ își manifestă o singură dată influența. Toate aceste operații au loc în același timp.

Cerință

Scrieți un program care să rezolve următoarele cerințe:

1. Care este cel mai mare număr prim din șirul inițial?
2. Care este suma dintre cel mai mic și cel mai mare număr din șirul obținut după ce toate numerele din șirul inițial își manifestă influența?

Date de intrare

Fișierul de intrare influent.in conține pe prima linie o valoare $c$ care poate să fie doar $1$ sau $2$, Pe a doua linie este un număr natural nenul $n$, pe a treia linie un șir de $n$ numere naturale nenule, separate prin câte un spațiu.

Date de ieșire

Dacă valoarea lui $c$ este $1$, atunci se va rezolva numai punctul 1 din cerință. În acest caz, fișierul de ieșire influent.out va conține pe prima linie numărul cerut.
Dacă valoarea lui $c$ este $2$, atunci se va rezolva numai punctul 2 din cerință. În acest caz, fişierul de ieşire influent.out va conține pe prima linie valoarea sumei cerute.

Restricții și precizări

• $n$ este număr natural, $1 \leq n \leq 50 \ 000$;
• Numerele de pe linia a treia a fișierului sunt numere naturale cuprinse între $2$ și $100 \ 000$;
• Pentru 12 puncte avem $c = 1$ și toate numerele din șir sunt prime;
• Pentru alte 22 puncte $c = 1$;
• Pentru 28 puncte avem $c = 2$ și toate numerele din șir sunt prime;
• Pentru 38 puncte avem $c = 2$.

Exemplul 1

influent.in

1
6
291 11 992 456 71 13

influent.out

71

Explicație

Cerința este 1. Cel mai mare număr prim din șir este $71$.

Exemplul 2

influent.in

2
5
12 10 100 5 6

influent.out

125

Explicație

Cerința este 2.
De exemplu, numărul aflat în șirul inițial pe poziția a $2$-a, cu valoarea $10$, are influența $2$ ($10 = 2 \cdot 5$) și afectează valoarea de pe poziția $2$ (poziția sa), valoarea de pe poziția $1$ și valorile de pe pozițiile $3$ și $4$. Observăm că în stânga este afectată o singură valoare întrucât sunt mai puțin de $k$ valori.
Șirul final este: $(21, 19, 112, 17, 13)$.
Suma dintre cel mai mic și cel mai mare număr din acesta este $13 + 112 = 125$.