bunicu

Bunicu

== include(page="template/taskheader" task_id="bunicu") ==

Bunicul s-a gandit sa ii faca o surpriza bunicii un sir binar de lungime $N$. Astfel, cei $N$ nepoti s-au strans si au creeat fiecare cate un sir binar de lungime $N$. Cand s-au dus la bunic sa il intrebe daca sirurile sunt bune, bunicul a zambit si dupa $3$ secunde a zis: "BA NUUUUU!!!!". Concluzia a fost ca cei $N$ nepoti trebuie sa gaseasca un al $N + 1$-lea sir binar de lungime $N$, diferit de cele initiale. Ajutati nepotii sa gaseasca un astfel de sir (sunt si ei suflete).

Bunicul s-a gandit sa ii faca o surpriza bunicii un sir binar de lungime $N$. Astfel, cei $N$ nepoti s-au strans si au creeat fiecare cate un sir binar de lungime $N$. Cand s-au dus la bunic sa il intrebe daca sirurile sunt bune, bunicul a zambit si dupa $3$ secunde a zis: "BA NUUUUU!!!!". Concluzia a fost ca cei $N$ nepoti trebuie sa gaseasca un al $N + 1$ - lea sir binar de lungime $N$, diferit de cele initiale. Ajutati nepotii sa gaseasca un astfel de sir (sunt si ei suflete).

h2. Date de intrare

Fişierul de intrare $bunicu.in$ va contine pe prima linie un numar natural $N$. Pe urmatoarele $N$ linii vor fi cele $N$ siruri binare de lungime $N$.

Fişierul de intrare $bunicu.in$ va contine pe prima linie un numar natural $T$, numarul de teste. Pe urmatoarele linii urmeaza cele $T$ seturi de teste: pe prima linie dintr-un set se citeste $N$. Urmatoarele $N$ linii vor fi cele $N$ siruri binare de lungime $N$.

h2. Date de ieşire

Fişierul de ieşire $bunicu.out$ va vontine o singura linie cu cel de al $N + 1$-lea sir binar de lungime $N$.

Fişierul de ieşire $bunicu.out$ va contine T linii. Pe linia $i$ se va afisa cel de al $N + 1$ - lea sir binar de lungime $N$ al setului $i$.

h2. Restricţii

* $1 ≤ N ≤ 3000$

* $1 ≤ T ≤ 5$
* $1 ≤ N ≤ 1000$
* Atentie la limita de memorie!
* Incercati sa rezolvati problema cu O(n^2^) timp si O(1) memorie

h2. Exemplu
table(example). |_. bunicu.in |_. bunicu.out |

|3

|1
3

000
010
110