extrapare

Un număr natural se numește extrapar dacă poate fi scris ca sumă de puteri distincte ale lui $2$, puteri care au exponent par. Numărul $0$ este considerat, de asemenea, extrapar. Considerând reprezentarea în baza $2$ pentru un număr natural, se numerotează pozițiile cifrelor din reprezentare, de la dreapta către stânga, începând cu $0$. Asupra reprezentării în baza $2$ trebuie să se efectueze o singură operație. Operația constă din eliminarea a exact $K$ cifre situate pe poziții consecutive.

Cerință

Fiind date reprezentările în baza $2$ pentru $N$ numere naturale, să se determine pentru fiecare dintre ele dacă se poate obține un număr extrapar în condițiile de mai sus.

Date de intrare

Fișierul de intrare extrapare.in conține pe prima linie două numere naturale N K, separate printr-un spațiu. Pe fiecare dintre următoarele $N$ linii se află reprezentarea în baza $2$ a unui număr natural.

Date de ieșire

Fișierul de ieșire extrapare.out va conține $N$ linii. Pe cea de a $i$-a linie ($1 \leq i \leq N$) se va afișa reprezentarea în baza $2$ a numărului extrapar obținut prin efectuarea unei singure operații asupra celei de a $i$-a reprezentări din fișierul de intrare, sau valoarea $−1$ dacă obținerea unui număr extrapar nu este posibilă în acest mod.

Restricții și precizări

• $0 < N \leq 10$;
• $0 \leq K <$ numărul de cifre din oricare reprezentare din fișierul de intrare;
• Orice reprezentare din fișierul de intrare are cel mult $1 \ 000 \ 000$ de cifre;
• Dacă există mai multe modalități de a efectua o operație astfel încât rezultatul să fie un număr extrapar, se va afișa rezultatul pentru acea operație în care poziția primei cifre eliminate este cea mai mare (cea mai din stânga poziție).
• Se garantează că reprezentările în baza $2$ din fișierul de intrare au cifra cea mai din stânga egală cu $1$.
• Reprezentarea în baza $2$ a numărului rezultat în urma efectuării operației se va afișa fără zerourile nesemnificative ce se pot forma la stânga lui.

Exemplu

extrapare.in

9 3
1001101
1010000010
101010001
111010100
100100
100010100
101000001
11110
101000

extrapare.out

-1
1010000
10001
10100
100
10100
1
-1
0

Explicație

Trebuie să eliminăm $3$ cifre pentru a forma numere extrapare.

• Numerele pentru care nu se poate obține un număr extrapar prin eliminarea a trei cifre de pe poziții consecutive sunt primul și al optulea.
• Din 1010000010 tăiem cifrele de pe pozițiile $0$, $1$ și $2$ și obținem 1010000.
• 101010001 este deja extrapar și vom elimina cele mai din stânga trei cifre.
• Observăm că dacă rezultatul este format doar din cifre egale cu $0$ se va afișa un singur $0$.

Și așa mai departe...