Un şir format din cifre trebuie să fie tastat în una sau mai multe sesiuni.

Există două tastaturi: tastatura A care conţine taste cu toate combinaţiile de exact două cifre: tasta 00, tasta 01, 02, …, 98, 99 și tastatura B care conţine taste cu toate combinaţiile de exact trei cifre: tasta 000, tasta 001, …, 998, 999. Cifrele se vor introduce în una sau mai multe sesiuni, pentru o sesiune putându-se folosi o singură tastatură. Datorită unei ordonanțe de urgență, dacă o combinație de taste a fost introdusă cu una din tastaturi în sesiunea curentă și, continuând sesiunea, această combinație poate fi introdusă din nou, este necesar să continuăm sesiunea cel puțin până când o vom introduce din nou. În cazul în care introducem până atunci și alte taste, trebuie să continuăm sesiunea până când vom introduce ultima apariție a lor.

Astfel, dacă şirul 255222255257 este început folosind tastatura A, se va scrie obligatoriu într‑o sesiune 25 52 22 25 52. Suntem obligați să tastăm până la ultima apariție a tastei 25 în sesiunea curentă, și când folosim tasta 52 suntem obligați să continuăm până la ultima apariție a acesteia. A se observa că cifrele de pe pozițiile subliniate sunt tot 2 și 5, însă nu formează o tastă care se poate apăsa în sesiunea curentă. Deoarece se dorește un număr cât mai mare de sesiuni, se va începe o nouă sesiune în care se va scrie doar 57.

Cerința

Cunoscându-se numărul total de cifre și secvența de cifre ce formează şirul, să se determine o modalitate de a despărţi textul astfel încât el să poată fi scris într-un număr maxim de sesiuni.

Date de intrare

Din fișierul text1.in se citesc:

• de pe prima linie un număr natural N reprezentând numărul de cifre
• de pe următoarea linie N cifre, scrise fără spații, reprezentând şirul de tastat

Date de ieșire

În fișerul text1.out se afișează:

• pe prima linie S, reprezentând numărul maxim de sesiuni
• pe fiecare dintre următoarele S linii, câte două numere p, k, scrise cu spaţiu între ele, fiecare astfel de pereche descriind, în ordinea în care apar în text, secvențele tipărite în sesiuni: p[i] – poziția din șirul de cifre dat unde începe sesiunea i și k[i] – tipul de tastatură folosită în sesiunea i (2 pentru tastatura A, 3 pentru tastatura B)

Restricții și precizări

• 3 ≤ n ≤ 1 000 000
• cifrele din secvență sunt între 0 și 9
• testele propuse asigură existența unei soluții pentru cerința dată
• dacă există mai multe soluții, se va furniza oricare dintre ele.
• pentru numărul corect de sesiuni, fără liniile care descriu soluția completă și corectă se acordă 50% din punctaj.

Exemplul 1

text1.in

15
233323333333322

text1.out

5
1 3
4 2
6 3
12 2
14 2

Explicație

Şirul poate fi scris în maximum 5 sesiuni astfel: (233) (32) (333 333) (33) (22)

• prima sesiune, începe cu prima cifră și foloseşte tastatura B (cu taste de 3 cifre)
• următoarea sesiune începe la cifra a 3-a și foloseşte tastatura A
• a treia sesiune începe la cifra a 6-a și foloseşte tastatura B
• a patra sesiune începe la cifra a 12-a și foloseşte tastatura A
• ultima sesiune începe la cifra a 14-a și foloseşte tastatura A

Exemplul 2

text1.in

8
46234623

text1.out

3
1 3
4 2
6 3

Explicație

Soluția corespunde secvenţelor (462) (34) (623).