### Problem Statement

John and Brus are training for a card game tournament. John is practicing his shuffling technique. John is using a deck of n cards, numbered 1 to n from top to bottom. This initial deck is called the main deck. There are three additional decks on the table, called the left, right and resulting decks. These three decks are initially empty. To shuffle the deck, John will repeat the following sequence of actions until the main deck contains less than two cards:

• Move one card from the top of the main deck to the top of the left deck, then one card from the top of the main deck to the top of the right deck, then one card from top of the main deck to the top of the left deck, and so on, until the main deck is empty.
• Repeat the following left times: Move one card from the top of the left deck to the bottom of the left deck.
• Repeat the following right times: Move one card from the top of the right deck to the bottom of the right deck.
• Move one card from the top of the left deck to the top of the resulting deck.
• Move one card from the top of the right deck to the top of the resulting deck.
• While the left deck is not empty, move one card from the top of the left deck to the top of the main deck.
• While the right deck is not empty, move one card from the top of the right deck to the top of the main deck.
If there is one card left in the main deck, John will move it to the top of the resulting deck. Return the number of the card at the top of the resulting deck after the shuffling is complete.

### Definition

 Class: TheCardShufflingDivOne Method: shuffle Parameters: int, int, int Returns: int Method signature: int shuffle(int n, int left, int right) (be sure your method is public)

### Constraints

-n will be between 1 and 1,000,000, inclusive.
-left and right will each be between 0 and 1,000,000, inclusive.

### Examples

0)

 `3` `0` `0`
`Returns: 1`
 The resulting deck will contain cards in the same order as the main deck at the beginning.
1)

 `3` `1` `1`
`Returns: 3`
 Here the order of cards in the resulting deck (from top to bottom) will be 3, 2, 1.
2)

 `5` `0` `0`
`Returns: 2`
3)

 `17` `12` `21`
`Returns: 17`

#### Problem url:

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

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13902&pm=10617

Vasyl[alphacom]

#### Testers:

PabloGilberto , ivan_metelsky , Chmel_Tolstiy

Search