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".
Problem Source: SPbSU ITMO contest. Petrozavodsk training camp. Winter 2008.