Claustrat

„Dormeau adânc sicriele de plumb,
Și flori de plumb și funerar veșmânt –”

Informatica trezește spiritul de poet din fiecare programator. Buclucașul Andi a învățat la ora de română despre poezia „Plumb”, scrisă de George Bacovia. Tânărul informatician a observat că termenul plumb este claustrat, adică vocala u este înconjurată de consoanele l și m. De atunci, băiatul, ori de câte ori vede un număr, se gândește doar la săracele cifre claustrate.

Într-un număr $X$, o cifră se numește claustrată dacă are atât în stânga, cât și în dreapta o cifră de paritate diferită. De exemplu, fiecare dintre numerele $456$, $878$ și $5321$ conține câte o cifră claustrată, anume: $5$, $7$, respectiv $2$. Pe de altă parte, numerele $12$, $334$ și $1024$ nu conțin nicio astfel de cifră. De asemenea, un șir de minimum două cifre consecutive se numește grup claustrat dacă acestea au aceeași paritate și sunt învecinate la stânga și la dreapta cu câte o cifră de paritate diferită.

Cerință

Dându-se $C$, cerința la care trebuie să răspundeți, și $N$ numere naturale, Andi vă roagă să răspundeți la una dintre următoarele două întrebări:

1. Câte cifre claustrate are fiecare număr?
2. Câte grupuri claustrate are fiecare număr?

Date de intrare

• Pe prima linie se va afla numărul $C$ al cerinței.
• Pe a doua linie se va afla $N$, numărul de numere.
• Pe a treia linie se vor găsi cele $N$ numere naturale, separate printr-un spațiu.

Date de ieșire

• Se vor afișa $N$ numere separate prin câte un spațiu, astfel încât al $i$-lea răspuns va corespunde numărului de pe poziția $i$.

Restricții și precizări

• $1 \leq C \leq 2$;
• $1 \leq N \leq 100 \ 000$;
• $1 \leq X \leq 10^{18}$;
• Un grup claustrat este format din cel puțin 2 cifre consecutive.
• Pentru citirea și afișarea rapidă, se recomandă folosirea acestor linii de cod la începutul funcției main:

ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

Exemplu 1

stdin

1  
5  
1010 55679 1234 3 27  

stdout

2 1 2 0 0  

Explicație

Mai jos, am evidențiat cifrele claustrate, aflate între |:
1|0|1|0, 55|6|79, 1|2|3|4, 3, 27

Exemplu 2

stdin

2  
6  
257546 833425 123456 22 49768332 27  

stdout

1 2 0 0 3 0  

Explicație

Mai jos, am evidențiat grupurile claustrate, aflate între |:
2|575|46, 8|33|42|5, 123456, 22, 4|97|68|33|2, 27