ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1622. Endspiel

Time limit: 2.0 second
Memory limit: 64 MB
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.
Problem illustration
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.

Input

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.

Output

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".

Samples

inputoutput
D4
B4-D4
C6-C4
A5-C5
...
C5-C3
B3-D3
D2-D4
D3
Impossible
Problem Source: SPbSU ITMO contest. Petrozavodsk training camp. Winter 2008.