Igauņu puisis Juka ir atradis vara stieples rituli. Uzzinājis, ka šāda veida produkciju krāsaino metālu uzpircēji nepieņem, viņš no stieples nolēmis izlocīt restītes šašlika cepšanai.

Restīšu formu attēlosim kā M × N rūtiņu tabulu. Tās rūtiņas, pa kurām iet stieple, apzīmētas ar zvaigznīti, pārējās – ar punktu. Katru robežu starp divām blakus zvaigznītēm stieple šķērso tieši vienu reizi. Caur vienu un to pašu rūtiņu stieple drīkst iet vairākas reizes, tā drīkst arī krustot sevi.

Uzrakstiet programmu, kas nosaka, vai ievaddatu failā doto formu iespējams aprakstītajā veidā izlocīt no viena stieples gabala!

Teksta faila stieple.dat pirmajā rindā doti divi naturāli skaitļi – tabulas augstums M un platums N (1 ≤ M, N ≤ 100), kas atdalīti ar tukšumsimbolu. Katrā no nākamajām M faila rindām dota N simbolu virkne. Zvaigznīte (*) apzīmē stieples ceļu, punkts (.) – tukšu rūtiņu; citu simbolu tabulā nav. Rindiņas numurēsim no augšas uz leju ar skaitļiem no 1 līdz M, bet kolonnas – no kreisās uz labo pusi no 1 līdz N.

Ja prasīto figūru izlocīt nav iespējams, teksta faila stieple.rez vienīgajā rindā izvadiet vārdu "NEVAR". Pretējā gadījumā pirmajā rindā izvadiet vārdu "VAR", otrajā rindā – vajadzīgo stieples garumu G (šķērsojamo rūtiņu robežu skaitu), kā arī stieples sākuma rindas un kolonnas numurus, starp katriem diviem skaitļiem liekot tukšumsimbolu, bet trešajā rindā – stieples locīšanas ceļu no sākuma rūtiņas, aprakstot to ar G simbolu virkni, kurā burti "Z", "A", "D" un "R" apzīmē attiecīgi virzīšanos par vienu rūtiņu uz augšu, pa labi, uz leju un pa kreisi. Ja iespējami vairāki atrisinājumi, izvadiet to, kuram sākuma rindas numurs ir vismazākais; ja tādi ir vairāki, tad no tiem izvēlieties variantu ar vismazāko sākuma kolonnas numuru; ja vēl aizvien ir vairāki varianti, izvadiet to, kuram locīšanas ceļu aprakstošā virkne ir vismazākā alfabētiskajā secībā.

3 8
***..***
*.****.*
***..***

VAR
19 2 3
DRRZZAADAAADAAZZRRD

Piezīme:
Pavisam ir 8 dažādi atrisinājumi – sākot no rūtiņas (2, 3), stiepli var izlocīt pa ceļu DRRZZAADAAADAAZZRRD, DRRZZAADAAAZAADDRRZ, ZRRDDAAZAAADAAZZRRD vai ZRRDDAAZAAAZAADDRRZ, bet no (2, 6) – pa ceļu DAAZZRRDRRRDRRZZAAD, DAAZZRRDRRRZRRDDAAZ, ZAADDRRZRRRDRRZZAAD vai ZAADDRRZRRRZRRDDAAZ.

Uzdevums izmantots Igaunijas informātikas olimpiādē 2002. gadā.