ciurulet

Popel, elev de liceu calificat la barajul pentru Lotul Național de Informatică, tocmai a învățat ciurul lui Eratostene, pentru aflarea numerelor prime, al cărui algoritm este descris astfel:

prim[i]=1, oricare ar fi i de la 2 la N 
pentru i de la 2 la N:
	dacă prim[i] este 1:
		pentru j de la 2*i la N din i în i:
			prim[j] = 0

Din cauza oboselii și a stresului, Popel a inițializat greșit șirul prim, punând pe unele poziții 0 în loc de 1. După ce a executat algoritmul pe șirul prim greșit inițializat, a obținut un nou șir pe care l-a notat pe o foaie de hârtie.

Mai târziu, nu își mai amintea șirul inițial prim, dar mai avea șirul final pe care l-a obținut. În plus, nu mai era sigur dacă unele valori din șirul final le-a notat corect, așa că le-a marcat cu caracterul ?. Popel vă roagă să aflați un șir inițial cu proprietatea că dacă ar executa algoritmul de mai sus asupra lui, ar obține un șir care s-ar potrivi cu șirul final notat pe foaie. De asemenea, el își dorește ca șirul inițial să aibă un număr cât mai mare de cifre de 1.

Date de intrare

Pe prima linie a fișierului ciurulet.in se va afla numărul N reprezentând valoarea până la care se execută algoritmul.

Următoarea linie conține N-1 caractere din mulțimea {0, 1, ?}, fără spații între ele, reprezentând șirul notat pe foaie. Caracterul ? indică un caracter pe care Popel nu și-l mai amintește (adică Popel nu mai știe dacă acolo era 0 sau 1). Al i-lea caracter dintre acestea reprezintă valoarea lui prim[i+1]. Dacă aceasta este diferită de ?, atunci Popel și-o amintește exact. Altfel, acolo ar fi putut fi orice (0 sau 1).

Date de ieșire

Pe prima linie a fișierului ciurulet.out se va afla numărul maxim de cifre de 1 care pot apărea într-un șir inițial din care se obține un șir final care se potrivește cu cel notat pe foaie.

Pe a doua linie se vor afișa N-1 caractere din mulțimea {0, 1}, fără spații între ele, care reprezintă șirul inițial folosit.

Restricții și precizări

• 2 ≤ N ≤ 1 000 000
• Pentru 30% din teste, șirul din fișierul de intrare nu conține caracterul ?.
• Pentru ca două șiruri A și B să se potrivească, trebuie ca A[i] și B[i] să fie egale, oricare ar fi i de la 2 la N cu B[i] diferit de ?. Cu alte cuvinte, peste 0 se potrivește 0, peste 1 se potrivește 1, iar peste ? se potrivesc atât 0, cât și 1.
• Se garantează faptul că șirul final obținut notat pe foaie este unul valid.
• Orice șir din care se obține șirul notat pe foaie în urma aplicării algoritmului de mai sus și care conține un număr maximal de 1 va fi considerat corect.
• Cele două șiruri sunt indexate de la poziția 2.

Exemple

ciurulet.in

6
10??0

ciurulet.out

4
10111

Explicaţii

Transformările prin care șirul 1011 va trece sunt: 10111 -> 10011 -> 10010
Șirul 10010 se potrivește cu ce și-a notat Popel pe foaie.

ciurulet.in

9
??10?00?

ciurulet.out

5
01101011

Explicaţii

Aplicând algoritmul de mai sus asupra șirului 01101011 se obține în final șirul 01100000, care se potrivește cu ce și-a notat Popel pe foaie.