# x increses to right, y increses to down

orig_piece = [(0, 0), (1, 0), (2, 0), (3, 0), (1, -1)]

def rotate(piece): # clock-wise 90 degree
    return [(-dy, dx) for (dx, dy) in piece]

def flip(piece):# horizontal
    return [(-dx, dy) for (dx, dy) in piece]

def solve(yn, xn):
    board = [None] * (xn * yn)
    if len(board) % len(orig_piece) != 0:
        raise ValueError("invalid size")
    if xn < yn:
        def index(x, y):
            return x + y * xn
        def parse(i):
            return i % xn, i // xn
    else:
        def index(x, y):
            return y + x * yn
        def parse(i):
            return i // yn, i % yn
    def show():
        def cell(x, y):
            n = board[index(x, y)]
            if n is None:
                return '.'
            elif n < 26:
                return chr(ord('A') + n)
            elif n < 52:
                return chr(ord('a') + n - 26)
        for y in xrange(yn):
            print " ".join(cell(x, y) for x in xrange(xn))
        print
    pieces = set()
    for i in xrange(len(orig_piece)):
        x0, y0 = orig_piece[i]
        piece = [(x - x0, y - y0) for (x, y) in orig_piece]
        def test(piece):
            for dx, dy in piece:
                if index(dx, dy) < 0:
                    return
            pieces.add(tuple(sorted(piece))) # need to sort
        for piece in (piece, flip(piece)):
            test(piece)
            for _ in xrange(3):
                piece = rotate(piece)
                test(piece)
    pieces = list(pieces)
    done = set()
    def f(i, count, shape):
        if count == len(board) // len(orig_piece):
            return True
        if shape in done:
            return False
        done.add(shape)
        for i in xrange(i, len(board)):
            if board[i] is None:
                break
        else:
            return False
        x, y = parse(i)
        for piece in pieces:
            for dx, dy in piece:
                if not(0 <= x + dx < xn and 0 <= y + dy < yn) or \
                    board[index(x + dx, y + dy)] is not None:
                    break
            else: # can place piece
                new_shape = shape
                for dx, dy in piece:
                    new_i = index(x + dx, y + dy)
                    board[new_i] = count
                    new_shape |= (1 << new_i)
                if f(i + 1, count + 1, new_shape):
                    return True
                for dx, dy in piece:
                    new_i = index(x + dx, y + dy)
                    board[new_i] = None
        return False
    if not f(0, 0, 0):
        raise ValueError("cannot be solved")
    show()

def main():
    import gc
    gc.set_debug(gc.DEBUG_STATS)
#   gc.set_threshold(100) # ???
    solve(5, 10) # sample
    solve(9, 20)
    solve(11, 20)
    solve(13, 20)
    solve(15, 14)

if __name__ == '__main__':
    main()