Тестирование шаффл-машин
У Сергея Михайловича очень интересная работа. Он занимается тестированием шаффл-машин - механизмов, используемых для тасования стопок карточек.
Машины, которые тестирует Сергей Михайлович, осуществляют перестановку стопок из 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-й сверху карточки в результирующей стопке, считая с единицы.