Tiles P87829

Your task is to write a program that tiles a rectangle f × c with tiles a × b. For each one of the 26 uppercase letters, there exactly is a vertical tile and a horizontal tile available, of which can be used at most one. For instance, if a = 1 and b = 3, we can use at most one of these two tiles:

The rectangle must be totally covered, and any piece of the used tiles can be left. If there are more than a way to tile, your prorgram must find the less in alphabetical order, reading from top to bottom and from left to right. In the case that does not exist any possible way, your program must indicate it.

Input

The input consists of a series of lines, each one with a, b, f and c in this order. All the numbers are between 1 and 50.

Output

For each line of the input, your program must print the least lexicographically tiling, or "!!!" if does not exist any. Separate the answers with a line in white.

Scoring

• TestA:  ‍15 Points ‍

  Some test cases will exclusively contain cases like the ones in the instance of input 1, in which a = 1, and where f and c are multiples of b.

• TestB:  ‍20 Points ‍

  Some test cases will also contain cases like the ones in the instance of input 2, in which f and c are multiples of a and b.

• TestC:  ‍65 Points ‍

  Other test cases will contain cases of every kind.