Atın səyahəti#3454
At hər dəfə eyni qara və ağ hüceyrələri görməkdən bezib və bütün dünyanı gəzmək istəyir. At bir istiqamətdə iki hüceyrə irəliləyib, sonra əvvəlki istiqamətə perpendikulyar bir hüceyrə hərəkət edə bilər. At öz dünyasında daha da irəliləmək istəyir. Bizim atımız adi 8\times8 lövhəsindən kiçik, lakin hələ də düzbucaqlı olan bir şahmat lövhəsində yaşayır. Siz bu macəraçı atın səyahətinə kömək edə bilərsinizmi?
Bunun üçün atın hər hüceyrəni yalnız bir dəfə ziyarət etdiyi bir yol tapmalısınız. Atın yolu lövhənin istənilən hüceyrəsində başlaya və bitə bilər.
Giriş məlumatları ilk sətirdə təbii ədədi ilə başlayır. Növbəti sətir test halının hər birinin təsvirini ehtiva edir. Hər bir test bir sətirdən ibarətdir və bu sətir və təbii ədədlərini ehtiva edir ki, 1 \leq p\times q\leq 26. Bu təsvir p\times q ölçüsündə bir şahmat lövhəsini təyin edir, burada müxtəlif hüceyrələri 1,\ldots,p ədədləri ilə təsvir edir və hüceyrələrin işarələrini müvafiq olaraq təsvir edir. Bunlar latın əlifbasının ilk hərfləridir: A, \ldots, Z.
Hər bir test halı üçün çıxış məlumatları "Scenario #i:" sətiri ilə başlamalıdır, burada test halının nömrəsidir, -dən başlayaraq. Sonra, atın şahmat lövhəsinin bütün hüceyrələrini ziyarət etdiyi leksikografik olaraq ilk yolu ehtiva edən bir sətir çıxarılmalıdır. Hər bir test halından sonra boş bir sətir çıxarın. Yolun təsvirini bir sətirdə, ziyarət edilən hüceyrələrin adlarını ardıcıl olaraq göstərərək çıxarın. Hər bir hüceyrənin adı böyük latın hərfi və ardınca bir rəqəmdən ibarətdir.
Əgər belə bir yol mövcud deyilsə, ayrıca bir sətirdə "impossible" yazılmalıdır.
Nümunə 1