### Problem Statement

You have a very simple computer whose memory consists only of two registers X and Y. Each of them can store a positive integer. The computer is so simple that it only has two different instructions (between brackets is the name of each instruction):

```[X] X := X + Y
[Y] Y := X + Y
```

As you may have imagined, both instructions compute the sum of both registers and store the result in one of them, overwriting its previous content. A program for this computer is simply a sequential list of zero or more instructions. When a program starts in this computer, both registers are initialized to 1. For instance, if the program is "XXYYX" then the following happens:

```  X | Y | ins | execute
----+---+-----+------------
1 | 1 | [X] | X := X + Y
----+---+-----+------------
2 | 1 | [X] | X := X + Y
----+---+-----+------------
3 | 1 | [Y] | Y := X + Y
----+---+-----+------------
3 | 4 | [Y] | Y := X + Y
----+---+-----+------------
3 | 7 | [X] | X := X + Y
----+---+-----+------------
10 | 7 |
```

You will be given an int r. Return the shortest program for the described computer that makes register X end with value r. Register Y may contain any value. If there are several such programs, return the one that comes earliest lexicographically.

### Definition

 Class: TwoRegisters Method: minProg Parameters: int Returns: String Method signature: String minProg(int r) (be sure your method is public)

### Notes

-A String comes lexicographically earlier than another one of the same length if and only if it contains a letter closer the beginning of the alphabet in the first position at which they differ.

### Constraints

-r will be between 1 and 1000000 (106), inclusive.

### Examples

0)

 `10`
`Returns: "XXYYX"`
 The example in the problem statement.
1)

 `3`
`Returns: "XX"`
2)

 `20`
`Returns: "XYYYYXX"`
3)

 `34`
`Returns: "XYXYXYX"`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10937

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14279&pm=10937

soul-net

#### Testers:

PabloGilberto , ivan_metelsky , zhuzeyuan

Math, Search