### Problem Statement

A permutation of the letters in an alphabet can be described by a string that contains each letter exactly once. For example, CABD describes the permutation of ABCD that maps A to C, B to A, C to B, and D to D. If we repeatedly apply that permutation, we will get the sequence ABCD,CABD,BCAD,ABCD,CABD,BCAD,ABCD,... This permutation is cyclic with length 3.

We want to find the permutation of the first n letters of

```    ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
```
that has the longest cycle. Create a class Permutation that contains the method best that takes the number of characters n as input and returns the lexicographically first permutation that has the maximum possible cycle length.

"Lexicographically first" means the String that would sort first among all the permutations of maximum cycle length, using the ASCII sequence (which sorts uppercase letters before lowercase letters).

### Definition

 Class: Permutation Method: best Parameters: int Returns: String Method signature: String best(int n) (be sure your method is public)

### Constraints

-n is between 1 and 52 inclusive

### Examples

0)

 `6`
`Returns: "ACBEFD"`
 This permutation has cycle length 6. So does BDEFCA, but ACBEFD is lexicographically first. The cycle is: ABCDEF -> ACBEFD -> ABCFDE -> ACBDEF -> ABCEFD -> ACBFDE -> ABCDEF
1)

 `7`
`Returns: "BCAEFGD"`
 This is the lexicographically first permutation with cycle length 12
2)

 `29`
`Returns: "BCDEAGHIJKLFNOPQRSTMVWXYZabcU"`
3)

 `1`
`Returns: "A"`
4)

 `8`
`Returns: "BCAEFGHD"`

#### Problem url:

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

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4605&pm=1135

dgoodman

#### Testers:

lbackstrom , brett1479

#### Problem categories:

Graph Theory, Math, String Manipulation