Înspăimântătorii tăi luptători au răpit-o pe Prinţesa Ghiocela şi au închis-o în castelul tău de pe vârful Muntelui Pleşuv. Deoarece eşti un geniu malefic, te-ai hotărât să îi oferi prinţesei iluzia unei şanse de evadare.
Castelul tău are forma unui caroiaj cu M linii şi N coloane. Cele MxN celule ale castelului sunt numerotate de la 1 la MxN în ordinea parcurgerii caroiajului pe linii de sus în jos, iar pe aceeaşi linie în ordinea coloanelor de la stânga la dreapta.
În fiecare dintre celulele castelului ai pus câte o cheie, mai precis celula i conţine cheia cu numărul i.
Evident, pentru a intra într-o cameră, prinţesa are nevoie de o anume cheie care permite deschiderea acesteia. Mai mult, dintr-o cameră prinţesa se poate deplasa într-un moment numai într-una dintre cele maxim patru camere adiacente pe orizontală şi verticală, doar dacă deţine cheia necesară deschiderii sale.
Odată ce a intrat într-o cameră şi a obţinut o cheie, prinţesa o păstrează şi poate să o utilizeze ori de câte ori doreşte.
Cerinţă
Deşi eşti convins că prinţesa nu va scăpa din castel, eşti curios să afli câte dintre cele MxN camere îi sunt accesibile. Date fiind dimensiunile castelului, camera în care se află iniţial prinţesa şi cheile necesare deschiderii fiecăreia dintre camere, află răspunsul la această întrebare presantă.
Date de intrare
Fişierul de intrare castel.in conţine pe prima linie trei numere naturale M N K separate prin câte un spaţiu reprezentând dimensiunile castelului, respectiv numărul camerei în care se află iniţial prinţesa. Urmează descrierea castelului. Pe fiecare dintre următoarele M linii se află câte N numere naturale cuprinse între 1 şi MxN reprezentând cheile necesare deschiderii fiecăreia dintre camere.
Date de ieşire
Fişierul de ieşire castel.out va conţine o singură linie pe care va fi scris un singur număr natural reprezentând numărul de camere accesibile prinţesei.
Restricţii
1 ≤ M, N ≤ 150
1 ≤ K ≤ M*N
Odată ce prinţesa a păşit într-o cameră, respectiva cameră va rămâne pentru totdeauna deschisă.
Exemple
castel.in
castel.out
Explicaţii
4 3 1
1 1 4
1 6 2
6 9 8
12 10 11
7
Prinţesa porneşte din camera 1. Aici foloseşe cheia 1 şi intră în camera 4. Se întoarce în camera 1 şi descuie camera 2. Foloseşte cheia luată din camera 4 şi descuie camera 3. În acest moment ea deţine cheile 1, 2, 3 şi 4. Foloseşte cheia 2 şi intră în camera 6, apoi foloseşte cheia 6 şi intră în camera 5, apoi în camera 4, de unde, folosind cheia luată din camera 6 intră în camera 7. La final prinţesa are cheile 1, 2, 3, 4, 5, 6, 7 şi nu mai poate deschide nici o altă cameră.
