Тестування шаффл-машин

Сергій Михайлович має дуже цікаву роботу. Він тестує машини тасування — механізми, які використовуються для перемішування стопок карт.

Машини, які тестує Сергій Михайлович, здійснюють перестановки в стопці з $n$ карт, де $n$ — парне натуральне число. Принцип їхньої роботи полягає у застосуванні до початкової стопки заданої послідовності перетворень, кожне з яких є одного з двох типів: U або D.

U-перетворення виконується так. Спочатку початкову стопку з $n$ карт ділять на дві частини: перша частина складається з верхніх $n/2$ карт, а друга — з нижніх $n/2$ карт. Потім нову стопку формують, почергово викладаючи по одній карті з кожної частини, починаючи з першої частини. D-перетворення відрізняється тим, що на другому кроці нову стопку починають формувати з другої частини, а не з першої.

Якщо пронумерувати карти зверху вниз як 1, 2, \ldots, n, то після U-перетворення карти у стопці розміщуватимуться зверху донизу у такому порядку: 1, n/2+1, 2, n/2+2, \ldots, n/2, n. Після D-перетворення порядок буде таким: n/2+1, 1, n/2+2, 2, \ldots, n, n/2.

Сергій Михайлович тестує машини так. Він бере $n$ карт, пронумерованих від $1$ до $n$, розташовує їх у стопці зі зростанням номерів від верху до низу, поміщає стопку до машини й виконує перемішування. Потім Сергій Михайлович бере $k$-ту карту зверху в отриманій стопці і, залежно від її номера, приймає рішення щодо працездатності машини.

Щоб пришвидшити тестування, Сергію Михайловичу потрібна програма, що обчислює номер $k$-тої карти зверху в результаті перемішування, якщо машина працює справно.