Șiruri

Fie $M$ un tablou bidimensional (matrice), format din $N$ linii şi $N$ coloane, având elemente din mulţimea $\{0, 1\}$. Liniile şi coloanele acestui tablou sunt numerotate de la $1$ la $N$. Un drum de lungime $K$ în acest tablou este un şir de perechi $(x_i, y_i)$, cu $i$ de la $1$ de la $K$, cu următoarele proprietăţi:

• $x_i$ și $y_i$ sunt valori numere naturale din intervalul $[1, N]$, pentru $i$ de la $1$ la $K$;
• $(|x_i - x_{i+1}|=1$ şi $y_i = y_{i+1})$ sau $(|y_i - y_{i+1}|= 1$ şi $x_i = x_{i+1}$), pentru $i$ de la $1$ la $K-1$.

Altfel spus, un drum este o succesiune de poziții în tablou astfel încât două poziții consecutive sunt alăturate fie sus-jos, fie stânga-dreapta. Numim valoare a unui drum șirul de valori $M[x_i][y_i]$, cu $i$ de la $1$ la $K$.

Prin anagramă a unui şir de valori vom înţelege orice rearanjare a elementelor acestuia. De exemplu, dacă şirul iniţial conţine elementele $(1, 0, 0, 1)$, atunci şirurile $(1, 0, 0, 1)$, $(1, 0, 1, 0)$, $(1, 1, 0, 0)$, $(0, 1, 1, 0)$ sunt anagrame ale acestuia.

Cerinţă

Cunoscând dimensiunea $N$ a tabloului, elementele tabloului $M$ și un șir $S$, compus din $K$ elemente din mulţimea $\{0, 1\}$, determinaţi un drum în tabloul $M$, având ca valoare o anagramă a lui $S$, dacă acest drum există.

Date de intrare

Datele de intrare se citesc din fişierul siruri.in, care are următoarea structură:

• pe prima linie se află două numere naturale $N$ și $K$, separate printr-un singur spaţiu, reprezentând dimensiunea tabloului, respectiv lungimea șirului $S$;
• pe fiecare din următoarele $N$ linii se află câte $N$ valori din mulţimea $\{0, 1\}$, separate prin câte un spațiu, reprezentând valorile tabloului $M$;
• pe linia $N+2$ se află $K$ numere, din mulţimea $\{0, 1\}$, separate prin câte un spațiu, reprezentând valorile șirului $S$.

Date de ieșire

Datele de ieşire se vor scrie în fişierul siruri.out, astfel:

• Dacă nu există niciun drum care satisface cerința problemei, atunci se va scrie valoarea $-1$ ;
• Dacă există un astfel de drum, atunci se vor scrie, pe linii separate, $K$ perechi de valori $x_i \ y_i$, din mulţimea $\{1,2, …,N\}$, separate printr-un singur spaţiu, reprezentând drumul determinat.

Restricții și precizări

• $1 ≤ N ≤ 100$
• $1 ≤ K ≤ 100 \ 000$
• Elementele tabloului $M$ și ale șirului $S$ sunt elemente din mulţimea $\{0, 1\}$
• Pentru teste în valoare de $20$ de puncte, şirul $S$ se găseşte pe o linie sau pe o coloană a matricei, aşa cum este dat în fişierul de intrare sau în ordine inversă;
• Soluția nu este unică, se acceptă orice soluție

Exemplul 1

siruri.in

3 10
0 0 0
0 1 1
1 0 1
1 1 1 0 1 1 1 0 1 1

siruri.out

2 2
2 3
2 2
2 1
2 2
2 3
2 2
2 3
3 3
3 2

Explicație

Valoarea obţinută pentru drumul din fişierul de ieşire este $(1, 1, 1, 0, 1, 1, 1, 1, 1, 0)$ şi reprezintă o anagramă a şirului dat.

Exemplul 2

siruri.in

4 3
1 0 0 0
0 0 1 0
1 0 0 0
1 0 0 0
1 1 0

siruri.out

4 1
3 1
2 1

Explicație

Şirul $S$ se găseşte pe coloana $1$ a matricei.

Exemplul 3

siruri.in

2 4
0 0
0 0
1 0 1 0

siruri.out

-1

Explicație

În tablou nu există valoarea $1$, deci nu se poate obține un drum a cărui valoare să conțină $1$.