შევსებული კროსვორდი

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 64 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: COCI, 2007/08, #2


მოცემულია შევსებული კროსვორდი, რომელიც შედგება R×C უჯრისაგან. ყველა უჯრაში წერია ლათინური სიმბოლო ან '#', რომელიც ბლოკირებულ უჯრებს აღნიშნავს. სიტყვები კროსვორდში წერია ვერტიკალურად ზემოდან ქვემოთ ან ჰორიზონტალურად მარცხნიდან მარჯვნივ.  სიტყვის სიგრძე უნდა აღემატებოდეს ერთ სიმბოლოს. დაწერეთ პროგრამა, რომელიც კროსვორდში ჩაწერილი სიტყვებიდან იპოვის ლექსიკოგრაფიულად ყველაზე მცირეს.

შესატანი მონაცემები: პირველ სტრიონში ორი მთელი რიცხვი R და C (2 ≤ R, C ≤ 20), სტრიქონებისა და სვეტების რაოდენობა კროსვორდში. მომდევნო R სტრიქონიდან თითოეულში მოცემულია C სიმბოლო. თითოეული სიმბოლო წარმოადგენს ან ლათინური დაბალი რეგისტრის სიმბოლოს ან '#'-ს, რომელიც ბლოკირებულ უჯრას აღნიშნავს. შესატანი მონაცემები ყოველთვის უზრუნველყოფენ ამოხსნის არსებობას.

გამოსატანი მონაცემები: ლექსიკოგრაფიულად უმცირესი სიტყვა.




მაგალითები

შესატანი მონაცემები
4 4 luka o#a# kula i#a# დაკოპირება
გამოსატანი მონაცემები
kala დაკოპირება
შესატანი მონაცემები
4 5 adaca da##b abb#b abbac დაკოპირება
გამოსატანი მონაცემები
abb დაკოპირება