### Problem Statement

In the classic Towers of Hanoi problem, there are three pegs, labeled A, B and C, and n discs, of sizes 1 to n. Each disc has a hole in the center, so that it can be placed on a peg. Initially, all the discs are stacked on peg A in order of size, with the smallest disc on top. Only one disc may be moved at a time. In each move, you remove the top disc from one of the pegs, and place it on another peg. A disc may be placed on an empty peg or stacked on top of a larger disc, but it may not be placed on top of a smaller disc.

target is a string consisting of n characters, each of which is either A, B or C. The goal of the game is to make the minimum number of moves so that character i of target is the peg containing the disc of size i + 1. There is only one shortest sequence of moves. Return the state of the game after making moves of these moves, in the same format as target.

### Definition

 Class: HanoiState Method: partwayState Parameters: String, int Returns: String Method signature: String partwayState(String target, int moves) (be sure your method is public)

### Constraints

-target will contain between 1 and 30 characters, inclusive.
-Each character of target will be either 'A', 'B' or 'C'.
-moves will be between 0 and m, inclusive, where the shortest solution to the game takes m moves.

### Examples

0)

 `"CCC"` `4`
`Returns: "BBC"`
 The full sequence of states is AAA, CAA, CBA, BBA, BBC, ABC, ACC, CCC. After 4 moves the state is BBC.
1)

 `"AAC"` `7`
`Returns: "AAC"`
2)

 `"AAAAAAAAAAAAAAAAAAAAAAAAAAAA"` `0`
`Returns: "AAAAAAAAAAAAAAAAAAAAAAAAAAAA"`
3)

 `"ABCABCABCABCABCABCABCABCABCABC"` `100000000`
`Returns: "CCCCCCCCBAAAABBBBACBAAAAACBAAA"`

#### Problem url:

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

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10798&pm=8303

bmerry

#### Testers:

PabloGilberto , Olexiy , marek.cygan , ivan_metelsky

#### Problem categories:

Recursion, Simulation