Şeful meu a plecat, pentru prima oară în viaţă, la New York. În timp ce aştepta un taxi într-o intersecţie, el a fost răpit. Răpitorii l-au urcat într-o maşină cu scopul de a-l duce către ascunzătoarea lor secretă. Fiind evident că şeful nu cunoaşte oraşul, ei nu l-au legat la ochi, aşa că el a reuşit să memoreze drumul urmat de maşină.
Oraşul arată ca o matrice formată din blocuri foarte înalte (zgârie-nori), între oricare două blocuri alăturate existând o stradă. Eu am o hartă pe care străzile sunt numerotate de la 1 începând de sus în jos şi respectiv de la stânga la dreapta. Pe hartă este marcată înălţimea fiecărui bloc.
Şeful meu îmi trimite prin SMS înălţimile blocurilor pe lângă care trece (cel din stânga şi cel din dreapta).
Când ajunge într-o intersecţie şoferul poate să o ia la dreapta, la stânga, înainte sau înapoi.
Când ajunge la ascunzătoarea răpitorilor, şeful meu îmi scrie un ultim mesaj în care îmi cere să determin locaţia intersecţiei de străzi în care se află ascunzătoarea răpitorilor şi să o comunic poliţiei.
Cerinţă
Scrieţi un program care, analizând harta oraşului şi indicaţiile şefului să determine toate posibilele locaţii ale ascunzătorii răpitorilor.
Date de intrare
Fişierul de intrare ny.in conţine pe prima linie două numere naturale separate prin spaţii, N şi M reprezentând numărul de linii şi respectiv numărul de coloane din matricea care reprezintă harta oraşului.
Pe fiecare dintre următoarele N linii se află câte M numere naturale nenule, reprezentând înălţimile zgârie-norilor din oraş.
Pe următoarea linie este scris un număr natural Lg, reprezentând lungimea traseului străbătut.
Pe următoarea linie sunt scrise Lg numere naturale nenule separate prin spaţii, reprezentând înălţimile blocurilor de pe traseu, aflate în stânga şefului.
Pe ultima linie sunt scrise Lg numere naturale nenule separate prin spaţii, reprezentând înălţimile blocurilor de pe traseu, aflate în dreapta şefului.
Date de ieşire
Fişierul de ieşire ny.out va conţine locaţiile posibile ale ascunzătorii răpitorilor, câte o locaţie pe linie. Acestea vor fi afişate în ordinea crescătoare a liniilor şi, dacă există mai multe locaţii cu aceeaşi linie, în ordinea crescătoare a coloanelor. Pentru fiecare locaţie sunt scrise două numere naturale separate printr-un spaţiu L şi C, reprezentând linia (strada orizontală) şi coloana (strada verticală) intersecţiei în care se află ascunzătoarea.
Restricţii
3 ≤ N, M ≤ 100
1<=Lg<=10000
Înălţimea oricărui bloc este ≤ 10000 de etaje.
Locatiile intersectiilor in care se poate afla ascunzatoarea au linia cuprinsa intre 1 si N, respectiv coloana cuprinsa intre 1 si M.
