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

1693. Loyd's Problem

Time limit: 1.0 second
Memory limit: 64 MB
Sam Loyd is a famous american puzzle creator. One of his most famous puzzles is “The 15 puzzle”. Also he is an author of many chess puzzles and cutting problems. Now you can try to solve his problem about cutting a chessboard.
You are given an n × n chessboard. Your goal is to cut it into the maximal number of pieces so that any two pieces are different. Each piece must consist of one or more cells and represent a side-connected region. If one piece can be obtained from another by a sequence of rotations then these pieces are considered equal. For example, there are two one-cell pieces: black cell and white cell and only one two-cell piece.
Here is one of possible solutions of the original Loyd's problem about cutting an 8 × 8 chessboard in 18 different pieces:
Problem illustration

Input

The first line contains the only integer n, the length of the chessboard side (1 ≤ n ≤ 30).

Output

In the first line output the maximal number of different pieces the chessboard can be cut into. Then output the required cutting: n lines with n lowercase latin letters in each of them. Each piece must consist of the same letters, one letter can be used for representing several pieces, but every two pieces sharing a common side must be represented by different letters (see example for further clarification). If there are several optimal cuttings, you can output any of them.

Sample

inputoutput
8
18
aaaacaaa
bbbcccba
baddabbb
aacdacba
accdacaa
babdccbb
baaadbba
babbaaaa
Problem Author: Sam Loyd feat. Igor Chevdar
Problem Source: Ural SU Contest. Petrozavodsk Winter Session, February 2009