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

USU Junior Championship March'2004

About     Problems     Submit solution     Judge status     Standings
Contest is over

I. Knight

Time limit: 1.0 second
Memory limit: 64 MB
Even paratroopers have vacations. The flight to Sirius in the depths of “The Admiral Brisco” Leo Hao whiled away with chessboard. No, he did not like usual chess game, and in addition, he did not have likely rival. The whole day Leo amused himself with an interesting thing: he tried to travel over all cells of the chessboard with the knight so that the knight visited each cell only one time. Leo attempted one time, then second, but always something was wrong. Leo became a little angry. Then he attempted board 4*4 instead of 8*8. Again failure after failure. A little angry, with the chessboard under his arm, Leo went to look for a local programmer. They two together indeed will solve this problem.

Input

The only line contains an integer N (1 ≤ N ≤ 8).

Output

If it is possible to travel with the knight over the square field N×N cells, then output should contain N2 lines with tour over the chessboard with mentioned property, otherwise the only word “IMPOSSIBLE”.

Samples

inputoutput
3
IMPOSSIBLE
5
a1
c2
e1
d3
e5
c4
d2
e4
c5
a4
b2
d1
e3
d5
b4
a2
c1
e2
c3
b1
a3
b5
d4
b3
a5

Notes

If you have solved this problem, pay attention to the problem "Knight Mare".
Problem Author: Folklore. Prepared by Den Raskovalov
Problem Source: IX Open Collegiate Programming Contest of the High School Pupils (13.03.2004)
To submit the solution for this problem go to the Problem set: 1298. Knight