Задачі
Мандрівка коня
Мандрівка коня
\includegraphics{https://static.e-olymp.com/content/2d/2d6d17518078e2ee748774d32fba0dd0e5b6089e.jpg}
Коню сумнно бачити одні й ті ж чорні та білі клітинки кожен раз знову і знову, і він вирішив здійснити подорож по усьому світу. Кінь може переміщуватись на дві клітинки у одному напрямку і на одну клітинку у напрямку, перпендикулярному до попереднього. Кінь подорожує по своєму світу усе далі і далі. Наш кінь живе на шаховій дошці, яка має меншу площу, ніж звична дошка \textbf{8}×\textbf{8}, але все ж є прямокутною. Чи можете ви допомогти цій авантюрній задумці коня здійснити свою подорож?
Для цього вам необхідно знайти такий шлях, на якому кінь відвідує кожну клітинку лише один раз. Шлях коня може починатись і завершуватись у довільній клітинці дошки.
\InputFile
Вхідні дані починаються з натурального \textbf{n} у першому рядку. Наступні \textbf{n} рядків містять описи кожного з \textbf{n} тестових випадків. Кожен тест складається з одного рядка, який містить два натуральних числа \textbf{p }та \textbf{q} таких, що \textbf{1} ≤ \textbf{p}×\textbf{q} ≤ \textbf{26}. Цей опис задає шахову дошку розміром \textbf{p}×\textbf{q}, де \textbf{p }описує різні клітинки числами \textbf{1}, ..., \textbf{p}, а \textbf{q} описує позначення клітинок літерами відповідно. Це перші \textbf{q} літер латинського алфавіту: \textbf{ A}, ..., \textbf{Z} .
\OutputFile
Вихідні дані для кожного тестового випадку розпочинаються з рядка, який містить "\textbf{Scenario #i:}", де \textbf{i -} це номер тестового випадку, починаючи з \textbf{1}. Далі необхідно вивести один рядок, який містить лексикографічно перший шлях, слідуючи по якому кінь відвідає усі клітинки шахової дошки. Після кожного тестового випадку виводьте порожній рядок. Опис шляху виводьте у одному рядку, послідовно вказуючи імена відвіданих клітинок. Ім'я кожної клітинки складається із великої латинської літери, за якою йде число.
Якщо такого шляху не існує, необхідно вивести у окремому рядку\textbf{ }"\textbf{impossible}".
Вхідні дані #1
3 1 1 2 3 4 3
Вихідні дані #1
Scenario #1: A1 Scenario #2: impossible Scenario #3: A1B3C1A2B4C2A3B1C3A4B2C4