Alchimie

Merg sigur, dar încet. Nu e foarte grea, e numai alchimie!
– Jean Carapace

În laboratoarele Marii Ghilde, ucenicul Jean Carapace are pe masa de lucru $N$ eprubete așezate în linie. Eprubetele sunt numerotate de la stânga la dreapta cu indici de la $1$ la $N$. Fiecare eprubetă $i$ conține inițial o cantitate de Esență Primordială, $V_i$, număr natural nenul. Definim o „Pereche Pură” ca fiind două eprubete vecine ale căror cantități sunt reprezentate prin numere prime între ele, adică $\text{cmmdc}(V_i, V_{i+1}) = 1$. O proprietate esențială a configurației inițiale este că se garantează existența a cel puțin unei astfel de perechi.

Scopul lui este să obțină „Scara Perfectă”, adică o configurație în care cantitatea de esență din fiecare eprubetă este egală cu indicele ei:

Pentru a modifica nivelul substanței, el poate folosi doar fenomenul de Rezonanță între două eprubete vecine. Mai exact, operațiile se aplică pe două eprubete situate la indicii $A$ și $B$, cu condiția ca $|A - B| = 1$. Operațiile permise sunt:

• adun A B $\implies V_A \leftarrow V_A + V_B$ (Eprubeta $A$ câștigă o cantitate de esență egală cu valoarea din eprubeta $B$)
• scad A B $\implies V_A \leftarrow V_A - V_B$ (Eprubeta $A$ pierde o cantitate de esență egală cu valoarea din eprubeta $B$)

La aplicarea operațiilor, trebuie respectate următoarele reguli:

1. La fiecare operație, doar eprubeta cu indicele $A$ își modifică valoarea. Eprubeta cu indicele $B$ rămâne neschimbată.
2. Cantitatea de esență din orice eprubetă trebuie să se mențină în intervalul de siguranță $[1, 10^5]$ în orice moment (inclusiv intermediar).
3. Numărul total de operații nu poate depăși $10^6$.

Cerință

Se cunosc $C$ (numărul cerinței, $1$ sau $2$), $N$ numărul de eprubete, precum și valorile $V_i$. Determinați:

1. Secvența de lungime maximă din șir în care oricare două eprubete alăturate formează o Pereche Pură, dacă $C = 1$. Dacă există mai multe astfel de secvențe, se va afișa cea cu indicele de început minim.
2. O succesiune de operații care transformă șirul inițial în Scara Perfectă, respectând toate regulile de mai sus, dacă $C = 2$.

Date de intrare

Fișierul de intrare alchimie.in conține:

• Pe prima linie: două numere naturale $C$ și $N$, cu semnificația din enunț.
• Pe a doua linie: $N$ numere naturale $V_1, V_2, \dots, V_N$, separate prin câte un spațiu, reprezentând cantitățile inițiale de esență din fiecare eprubetă.

Date de ieșire

Fișierul de ieșire alchimie.out va conține:

• Două numere naturale $P_{inceput}$ și $P_{final}$, separate prin exact un spațiu, reprezentând indicii de început, respectiv de final ai secvenței determinate, dacă $C = 1$.
• Dacă $C = 2$:
  • Pe prima linie numărul total de operații $K$.
  • Pe următoarele $K$ linii operațiile în formatul tip_operatie A B, câte o operație pe fiecare linie.

Restricții și precizări

• $2 \le N \le 10^4$;
• $1 \le V_i \le 10^5$ atât inițial, cât și în orice moment intermediar;
• Se garantează existența soluției respectând limita de maximum $10^6$ operații pentru $C = 2$;
• Se garantează că există cel puțin o Pereche Pură în șirul dat.

Exemplul 1

alchimie.in

1 5
10 5 12 7 14

alchimie.out

2 4

Explicație

Perechea $(10, 5)$ are $\text{cmmdc}(10, 5) = 5 \ne 1$. Perechea $(5, 12)$ are $\text{cmmdc}(5, 12) = 1$. Perechea $(12, 7)$ are $\text{cmmdc}(12, 7) = 1$. Perechea $(7, 14)$ are $\text{cmmdc}(7, 14) = 7 \ne 1$.

Exemplul 2

alchimie.in

2 2
2 3

alchimie.out

3
scad 2 1
scad 1 2
adun 2 1

Explicație