text

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 $255222255\underline{25}7$ 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ţă

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 text.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 text.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

• 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.

Exemple

text.in

15
233323333333322

text.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 tastaturaB (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

text.in

8
46234623

text.out

3
1 3
4 2
6 3

Explicație

Soluția corespunde secvenţelor 462 34 623