Covering a board P27459


Statement
 

pdf   zip

thehtml

You have an n × m board. In how many ways can you cover it with 1 × 2 pieces?

Input

Input consists of n and m. You can assume 2 ≤ nm ≤ 52, and that nm is even.

Output

Print in lexicographical order all the ways to cover the board. To distinguish the pieces, both cells must have the same lowercase letter, and all the pieces must have different letters. Appart from that, letters should be as small possible. Print an empty line after each solution.

Public test cases
  • Input

    1 2
    

    Output

    aa
    
    
  • Input

    2 2
    

    Output

    aa
    bb
    
    ab
    ab
    
    
  • Input

    2 4
    

    Output

    aabb
    ccdd
    
    aabc
    ddbc
    
    abbc
    addc
    
    abcc
    abdd
    
    abcd
    abcd
    
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++