Тестування шаффл-машин
У Сергія Михайловича дуже цікава робота. Він займається тестуванням шаффл-машин - механізмів, які використовуються для тасування стопок карток.
Машини, які тестує Сергій Михайлович, здійснюють перестановку стопок з n карток, де n - парне натуральне число. Механізм, за яким вони працюють, полягає у застосуванні до заданої стопки певної послідовності перетворень, кожне з яких може бути одним з двох типів - U або D.
U-перетворення відбувається наступним чином. Спочатку задана стопка з n карток ділиться на дві частини, перша з яких складається з n / 2 верхніх карток, а друга - з n / 2 нижніх. Потім у результуючу стопку по черзі поміщається по одній картці з кожної з двох частин, починаючи з першої. D-переотворення відрізняється від U-перетворення лише тим, що на другому кроці результуюча стопка починає формуватись починаючи не з першої частини, а з другої.
Якщо ми пронумеруємо картки зверху до низу числами 1, 2, ..., n, то в результаті U-перетворення картки будуть йти зверху до низу у порядку 1, n / 2 + 1, 2, n / 2 + 2, ..., n / 2, n, а в результаті D-перетворення порядок карток буде таким: n / 2 + 1, 1, n / 2 + 2, 2, ..., n, n / 2.
Сергій Михайлович проводить тестуваня наступним чином. Він бере n карток, пронумерованих від 1 до n, і форує з них стопку так, щоб номери карток у стопці зростали при їх перегляді зверху до низу. Потім він поміщає стопку у машину і проводить її перетасування. Після цього Сергій Михайлович дістає з результуючої стопки k-ту зверху картку і у залежності від її номеру робить висновок про справність чи несправність тестуючої машини.
Для прискорення процесу тестування Сергію Михайловичу потрібна програма, яка обчисляє, яким буде номер k-ї зверху картки у результуючій стопці, якщо шаффл-машина працюєт коректно.
Вхідні дані
Перший рядок містить цілі числа n і k (1 ≤ k ≤ n ≤ 2 * 10^9, число n - парне). У другому рядку записано від 1 до 1000 символів 'U' і 'D' без пропусків. Ці символи описують послідовність перетворень, які застовуються машиною для перестановки карток. Символ 'U' відповідає U-перетворенню, а символ 'D' - D-перетворенню.
Вихідні дані
Вивести одне ціле число - номер k-ї зверху картки у результуючій стопці, починаючи з одиниці.