ENG  RUS Timus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

## SPbSU ITMO contest. Petrozavodsk training camp. Winter 2008

Соревнование завершено

## E. Endspiel

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
There is a game called "Yoga". On the game board there are 32 checkers, standing as shown on the picture. Each turn a checker jumps over another one and lands on a free cell — almost like in the checker game, but vertically or horizontally, not diagonally. The checker which was jumped over is removed from the board.
We will look at endspiel, the last part of the game. Imagine that there is only one checker left. Given its location, find a possible sequence of turns that leads to this endspiel.

### Исходные данные

Let us introduce a coordinate system similar to the one that is used in the game of chess. The columns are numbered by Latin letters from A to G, the rows are numbered from 1 to 7. For example, a cell with coordinates "D4" is the central cell.
The first line contains the coordinates of the last checker in the notation described above.

### Результат

If it is possible to reach the specified endspiel, output the sequence of turns leading to it. Each turn should be printed in the following format: <start cell>–<finish cell>, where <start cell> is the coordinates of a cell where the moving checker is located before the turn, and <finish cell> is the coordinates of its destination cell. There will always be 31 turns.
If it is impossible to find the necessary sequence, output the word "Impossible".

### Примеры

исходные данныерезультат
D4
B4-D4
C6-C4
A5-C5
...
C5-C3
B3-D3
D2-D4
D3
Impossible
Источник задачи: SPbSU ITMO contest. Petrozavodsk training camp. Winter 2008.
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1622. Endspiel