nemo

Peștișorul Nemo are nevoie de ajutorul vostru! În arhipelagul său au apărut niște pescari ambițioși ce vor să exploateze zona. Arhipelagul lui Nemo poate fi reprezentat ca o matrice cu $N$ linii și $M$ coloane. Acesta este alcătuit din insule înconjurate de apă, unde o insulă reprezintă o zonă de celule adiacente pe linie sau coloană ce nu conține celule de apă pe interior și nu poate fi extinsă. Pe lângă insule, una dintre celule o reprezintă adăpostul lui Nemo, care nu se va afla pe o insulă (din motive evidente).

În arhipelag sunt celule controlate de pescari (acestea nu vor acoperi insule sau adăpostul lui Nemo). În fiecare zi, pescarii își vor extinde plasele cu o unitate pe o anumită direcție (linie sau coloană), dar în ambele sensuri (stânga și dreapta, respectiv sus și jos), atâta timp cât nu vor ieși din marginile arhipelagului. Aceștia vor avea direcția preferată determinată din prima zi, și va rămâne constantă pe parcursul tuturor zilelor. De asemenea, fiind oameni cinstiți, aceștia vor respecta următoarele reguli:

1. Un pescar nu se poate extinde peste pământ sau peste plasa altui pescar.
2. Dacă după o anumită zi un pescar nu se mai poate extinde pe un anumit sens, acesta va continua să se exindă pe sensul rămas.
3. Dacă doi pescari ar ajunge în aceeași zi pe aceeași celulă are prioritate cel aflat pe linia cu indicele mai mic, iar în caz de egalitate a liniilor, cel mai din stânga.

Cerință

Nemo se întreabă care este prima zi din care el nu va mai putea ajunge la adăpost din punctul său de start, știind că nu poate înota pe pământ, trece prin plasele pescarilor sau ieși din marginile arhipelagului. El se poate deplasa dintr-o celulă doar în cele adiacente pe linie sau coloană.

Date de intrare

Pe prima linie din fișierul nemo.in se vor afla două numere $N$ și $M$ reprezentând dimensiunile arhipelagului. Apoi vor urma $N$ linii, pe fiecare linie $M$ caractere care descriu arhipelagul în prima zi:

• Caracterul . reprezintă o celula cu apă
• Caracterul N reprezintă poziția lui Nemo
• Caracterul A reprezintă adăpostul lui Nemo
• Caracterul # reprezintă o zonă cu pământ
• Caracterul L reprezintă un pescar care își va extinde plasa doar pe linie (la stânga și la dreapta în fiecare zi cât timp nu iese din marginile arhipelagului)
• Caracterul C reprezintă un pescar care își va extinde plasa doar pe coloană (în sus și în jos în fiecare zi cât timp nu iese din marginile arhipelagului)

Date de ieșire

În fișierul nemo.out se va scrie un singur număr, reprezentând prima zi începând cu care Nemo nu va putea ajunge la adăpost. Dacă o astfel de zi nu există, se va afișa valoarea $−1$.

Restricții și precizări

• $2 \leq N \leq 1000$ și $2 \leq M \leq 1000$
• Se poate ca după o anumită zi o plasă să acopere adăpostul lui Nemo, caz în care el nu mai poate ajunge la adăpost.
• Se poate ca după o anumită zi o plasă să acopere punctul de start al lui Nemo, caz în care el nu mai poate ajunge la adăpost.
• Testele sunt grupate, spre deosebire de cum au fost în timpul concursului.

Exemplul 1

nemo.in

10 10
........L.
....C.....
.N........
..A...L...
..........
..........
..........
...#......
..###.....
.#####....

nemo.out

-1

Explicație

Așa va arăta arhipelagul în ziua a treia, unde plasele extinse ale pescarilor au fost notate de asemenea cu C, respectiv L:

....C.LLLL
....C.....
.N..C.....
..A.CLLLL.
..........
..........
..........
...#......
..###.....
.#####....

Pescarul de pe linia a doua s-a extins având prioritate și separă adăpostul lui Nemo de restul arhipelagului.

Exemplul 2

nemo.in

10 10
.N........
..........
..........
......L...
....L.....
..........
...#.....A
..###..LC.
.#####....
#######...

nemo.out

4

Explicație

Arhipelagul în ziua 4:

.N........
..........
..........
...LLLLLLL
.LLLLLLLC.
........C.
...#....CA
..###LLLC.
.#####..C.
#######.C.