Testing shuffle machines
Sergei Mikhailovich very interesting work. He is now testing shuffle machines - the mechanisms used for shuffling stacks of cards.
Machines that test Sergei Mikhailovich, perform a permutation of n stacks of cards, where n is an even integer. The mechanism by which they work is to apply to the original stack of a specific sequence of transformations, each of which has one of two types - U or D.
Machines that test Sergei Mikhailovich, perform a permutation of n stacks of cards, where n is an even integer. The mechanism by which they work is to apply to the original stack of a specific sequence of transformations, each of which has one of two types - U or D. U-transformation as follows. First, the initial stack of n cards is divided into two parts, the first of which consists of n / 2 top cards, and the second - from n / 2 lower. Then in the resulting stack alternately placed on one card from each of two parts, beginning with the first. D-conversion is different from the U-transformation except that the second step, the resulting pile begins to form, beginning not with the first part, but with the second.
If we enumerate the cards down the numbers 1, 2, ..., n, then the resulting U-transformation will follow the card from top to bottom in the order of 1, n / 2 + 1, 2, n / 2 + 2, ..., n / 2, n, and as a result of D-conversion will be the order of cards: n / 2 + 1, 1, n / 2 + 2, 2, ..., n, n / 2.
Sergei Mikhailovich is testing follows. He takes the n cards, numbered from 1 to n, and generates a stack of them so that the number of cards in the pile grew when viewed from the top down. He then places the pile in the car and makes her shuffle. After that Sergei Mikhailovich gets from the resulting stack of k-th top card, and depending on the number concludes serviceability or malfunction of the test machine.
To accelerate the testing process Sergei Mikhailovich need a program that calculates what will be equal number of k-th top card in the resulting pile, if you shuffle machine is working properly.
Input
The first line contains integers n and k (1 ≤ k ≤ n ≤ 2 * 10^9, number n is odd). The second line contains from 1 to 1000 characters 'U' and 'D' with no spaces. These characters describe the sequence of transformations applied by machine to swap cards. The symbol 'U' corresponds to the U-transformation and the symbol 'D' - D-conversion.
Output
Print one integer - the number of k-th top card in the resulting pile, starting with one.