Shibuya Scramble Crossing (formal name: 渋谷駅前 Shibuya Ekimae) is one of the must-sees for visitors in Tokyo. 4 buildings are located at the corners of the crossing, namely EKIMAE, JR, MAGNET and QFRONT. For simplicity, we name the corners using the building names.
This crossing is called a scramble crossing because the pedestrial traffic lights are synchronized and they turn green and red at the same time. It is possible to get from one corner to any other corner by crossing the intersection one time, except between EKIMAE and MAGNET because of its longer distance. You may refer to the layout above.
Now you are standing at the corner $$$X$$$ and you would like to get to corner $$$Y$$$. However, as you observe the people crossing the intersection, you notice that people cross the intersection many times in order to take videos. You have $$$K$$$ friends that you would like to call and show them the intersection. Therefore, you would like to cross the intersection exactly $$$K$$$ times and end up at corner $$$Y$$$. Can you make a plan or determine that it is not possible?
The first line contains a string $$$X$$$: EKIMAE, JR, MAGNET or QFRONT.
The second line contains a string $$$Y$$$: EKIMAE, JR, MAGNET or QFRONT.
The third line contains an integer $$$K$$$. ($$$1 \le K \le 1000$$$)
If it is impossible to go from $$$X$$$ to $$$Y$$$ using exactly $$$K$$$ crossings, output Impossible.
Otherwise, output $$$K$$$ lines. The $$$i^{th}$$$ line should contain a string that indicates your location after the $$$i^{th}$$$ crossing: EKIMAE, JR, MAGNET or QFRONT. Therefore, the last line should be same as $$$Y$$$. If there are multiple solutions, output any of them.
JRJR3
QFRONT MAGNET JR
MAGNETEKIMAE1
Impossible
