Şaffl-maşınların test edilməsi

Sergey Mixayloviçin çox maraqlı bir işi var. O, kart dəstələrinin qarışdırılması üçün istifadə olunan shuffle maşınlarını sınaqdan keçirir.

Sergey Mixayloviçin sınaqdan keçirdiyi maşınlar $n$ kartdan ibarət dəstə üzərində permutasiyalar yerinə yetirir, burada $n$ cüt təbii ədəddir. Maşınlar ilkin dəstəyə ard-arda verilmiş bir sıra transformasiyalar tətbiq edir və bunlardan hər biri iki növdən biri olur: U və ya D.

U-transformasiyası aşağıdakı kimi həyata keçirilir. Əvvəlcə, $n$ kartdan ibarət dəstə iki hissəyə bölünür: birinci hissə yuxarıdakı $n/2$ kartdan, ikinci hissə isə aşağıdakı $n/2$ kartdan ibarət olur. Sonra, yeni dəstə bu iki hissədən növbə ilə bir kart götürülməklə yığılır; ilk öncə birinci hissədən başlayaraq. D-transformasiyasında isə fərq ondadır ki, ikinci addımda yeni dəstə birinci hissədən deyil, ikinci hissədən başlayır.

Əgər kartları yuxarıdan aşağıya doğru 1, 2, \ldots, n kimi nömrələsək, U-transformasiyasından sonra kartlar yuxarıdan aşağıya doğru bu ardıcıllıqda olacaq: 1, n/2+1, 2, n/2+2, \ldots, n/2, n. D-transformasiyasından sonra isə ardıcıllıq belə olacaq: n/2+1, 1, n/2+2, 2, \ldots, n, n/2.

Sergey Mixayloviç maşınları aşağıdakı kimi yoxlayır. O, üzərində $1$-dən $n$-ə kimi nömrələnmiş $n$ kart götürür, onları dəstədə yuxarıdan aşağıya doğru artan qaydada düzür, dəstəni maşına yerləşdirir və qarışdırmanı həyata keçirir. Sonra Sergey Mixayloviç yaranmış dəstədə yuxarıdan $k$-cı kartı götürür və onun nömrəsindən asılı olaraq qərar verir ki, maşın düzgün işləyirmi ya yox.

Test prosesini sürətləndirmək üçün Sergey Mixayloviçə bir proqram lazımdır ki, düzgün işləyən shuffle maşınında nəticədə yuxarıdan $k$-cı kartın nömrəsini hesablaya bilsin.

Giriş

Birinci sətirdə iki tam ədəd $n$ və $k$ (1 \leq k \leq n \leq 2 \cdot 10^9, $n$ cütdür) verilir. İkinci sətirdə boşluq olmadan uzunluğu 1-dən 1000-ə qədər olan 'U' və 'D' simvollarından ibarət bir sıra verilir. Bu simvollar maşının kartları qarışdırmaq üçün tətbiq etdiyi transformasiya ardıcıllığını təsvir edir. 'U' simvolu U-transformasiyasına, 'D' isə D-transformasiyasına uyğundur.

Çıxış

Cəmi bir tam ədəd çap edin — nəticədə yuxarıdan $k$-cı kartın nömrəsini, birdən başlayaraq.