„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 asezate in linie. Eprubetele sunt numerotate de la stanga 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ă cmmdc(V[i] , V[i+1]) = 1. O proprietate esențială a configurației inițiale este că se garantează existent, 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:

Eprubeta ₁ = 1, Eprubeta ₂ = 2, …, Eprubeta _N = N.

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 ⇒ V[A] ← V[A] + V[B] (Eprubeta A câștigă o cantitate de esență egală cu valoarea din eprubeta B)
• scad A B ⇒ V[A] ← 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, 10sup>5] în orice moment (inclusiv intermediar).
3. Numărul total de operații nu poate depăși 106.

Cerințe

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], . . . , 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 Pinceput și Pfinal, 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 ≤ N ≤ 10 000;
  • 1 ≤ V[i] ≤ 100 000 atât inițial, cât și în orice moment intermediar;
  • Se garantează existența soluției respectând limita de maximum 106 operații pentru C = 2;
  • Se garantează că există cel puțin o Pereche Pură în șirul dat.

Exemplul 1

alchimie.in

5
1 2 3 4 5

alchimie.out

15

Explicație

Perechea (10, 5) are cmmdc(10, 5) = 5 ≠ 1. Perechea (5, 12) are cmmdc(5, 12) = 1. Perechea (12, 7) are cmmdc(12, 7) = 1. Perechea (7, 14) are cmmdc(7, 14) = 7 ≠ 1.

Exemplul 2

alchimie.in

2 2
2 3

alchimie.out

3
scad 2 1
scad 1 2
adun 2 1

Explicație

Șirul inițial este [2, 3]. Dorim să ajungem la [1, 2].

Operația 1: scad 2 1 ⇒ V[2] ← 3 − 2 = 1. Șirul devine [2, 1].
Operația 2: scad 1 2 ⇒ V[1] ← 2 − 1 = 1. Șirul devine [1, 1].
Operația 3: adun 2 1 ⇒ V[2] ← 1 + 1 = 2. Șirul devine [1, 2].

S-a obținut configurația dorită în doar 3 operații.