primprim

Pentru un număr natural a definim costul ca fiind valoarea absolută (modulul) diferenței dintre a și numărul prim cel mai apropiat de a. Asupra unui șir de $n$ numere naturale, situate pe poziții numerotate de la $1$ la $n$, se aplică, în ordine, o succesiune de $q$ operații. O operație constă dintr-o înlocuire și o afișare și este descrisă sub forma i x p, cu semnificația:

• mai întâi înlocuim cu $x$ elementul din șir de pe poziția $i$;
• apoi afișăm suma minimă totală a costurilor unor elemente convenabil selectate de pe $p$ poziții distincte din șir.

Cerință

Cunoscând $n$ și cele $n$ elemente ale șirului, scrieți un program care să determine:

1. suma costurilor tuturor elementelor din șirul dat;
2. rezultatele afișate în urma aplicării fiecăreia dintre cele $q$ operații, date în forma precizată.

Date de intrare

Fișierul de intrare primprim.in va conține pe prima linie un număr natural $C$, reprezentând cerința care trebuie să fie rezolvată ($1$ sau $2$), pe a doua linie numărul natural $n$, cu semnificația din enunț, iar pe a treia linie cele $n$ elemente din șir, în ordinea din șir.
Dacă $C = 2$, pe a patra linie se află numărul natural $q$, reprezentând numărul de operații, iar pe următoarele $q$ linii se află cele $q$ operații, câte o operație pe linie, în forma descrisă în enunț. Numerele scrise pe aceeași linie sunt separate prin câte un spațiu.

Date de ieșire

Dacă $C = 1$, fișierul de ieșire primprim.out va conține o singură linie pe care va fi afișată suma costurilor tuturor elementelor din șir.
Dacă $C = 2$, fișierul de ieșire primprim.out va conține $q$ linii, pe linia $i$ fiind scris rezultatul afișat după executarea celei de a $i$-a operații din fișierul de intrare.

Restricții și precizări

• $1 \leq q \leq 2 * 10^5$;
• $1 \leq i,p \leq n \leq 10^6$; $1 \leq x \leq 10^6$;
• Elementele șirului sunt numere naturale nenule $\leq 10^6$;
• Pentru $20$ de puncte, $C = 1$, $n = 1$;
• Pentru $22$ de puncte, $C = 1$, $1 \lt n \leq 1 \ 000$;
• Pentru $28$ de puncte, $C = 2$, $n \leq 1 \ 000$, $q \leq 10$;
• Pentru $30$ de puncte, $C = 2$ și nu există restricții suplimentare.

Exemplul 1

primprim.in

1
5
8 1 3 5 9

primprim.out

4

Explicație

$C = 1, n = 5$, iar șirul este $8, 1, 3, 5, 9$. Costurile elementelor sunt, în ordine, $1, 1, 0, 0, 2$, deci suma este $4$.

Exemplul 2

primprim.in

2
5
8 1 3 5 9
3
2 6 4
3 5 2
5 12 5

primprim.out

2
0
3

Explicație

$C = 2, n = 5$, iar șirul inițial este $8, 1, 3, 5, 9$. Se aplică șirului $3$ operații:

• După prima operație, pentru care $i = 2$, $x = 6$ și $p = 4$, șirul devine $8, 6, 3, 5, 9$. Suma minimă totală se obține dacă selectăm valorile de pe pozițiile $1, 2, 3$ și $4$, costurile fiind $1+1+0+0=2$.
• După a doua operație, pentru care $i = 3$, $x = 5$ și $p = 2$, șirul devine $8, 6, 5, 5, 9$. Selectăm valorile de pe pozițiile $3$ și $4$ (acestea având costul $0$).
• După a treia operație, pentru care $i = 5$, $x = 12$ și $p = 5$, șirul devine $8, 6, 5, 5, 12$. Selectăm toate valorile, deci suma este $1 + 1 + 0 + 0 + 1 = 3$.