### Problem Statement

```  S ::= T | bUa
T ::= aTb | A | B
U ::= aU | bU | a | b
A ::= aA | a
B ::= bB | b
```
Displayed above is a Context-Free Grammar (CFG). You begin with the string (quotes for clarity) "S", and apply replacement rules until your resulting string no longer contains any capital letters. The first line above says that S can be replaced with T or bUa. The other lines are similar. You will return a sequence of strings, beginning with "S" and ending with input, where each successive sequence element results from applying one of the replacement rules above. For example, if input is "aaabb" then you will return
` {"S","T","aTb","aaTbb","aaAbb","aaabb"}`

### Definition

 Class: DerivationDisplay Method: getDerivation Parameters: String Returns: String[] Method signature: String[] getDerivation(String input) (be sure your method is public)

### Constraints

-input will contain between 1 and 50 characters inclusive.
-Each character in input will be 'a' or 'b'.
-There will be exactly one solution.

### Examples

0)

 `"aaabb"`
`Returns: {"S", "T", "aTb", "aaTbb", "aaAbb", "aaabb" }`
 The example above.
1)

 `"bbba"`
`Returns: {"S", "bUa", "bbUa", "bbba" }`
 In the first step, S must be replaced with bUa in order to derive this string. Then the 2 inner b's are added.
2)

 `"baabba"`
`Returns: {"S", "bUa", "baUa", "baaUa", "baabUa", "baabba" }`
3)

 `"a"`
`Returns: {"S", "T", "A", "a" }`
4)

 `"b"`
`Returns: {"S", "T", "B", "b" }`
5)

 `"aabbbbbbbb"`
```Returns:
{"S",
"T",
"aTb",
"aaTbb",
"aaBbb",
"aabBbb",
"aabbBbb",
"aabbbBbb",
"aabbbbBbb",
"aabbbbbBbb",
"aabbbbbbbb" }```

#### Problem url:

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

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=6533&pm=4021