Ş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 şaffl-maşınların test edilməsi ilə məşğuldur.
Sergey Mixayloviçin test etdiyi maşınlar n kartdan ibarət dəstələrin yerini dəyişir, burada n cüt təbii ədəddir. Bu maşınlar müəyyən bir çevrilmə ardıcıllığını tətbiq edərək işləyir, hər çevrilmə iki növdən biri ola bilər: U və ya D.
U çevrilməsi belə həyata keçirilir: Əvvəlcə n kartdan ibarət dəstə iki bərabər hissəyə bölünür. Birinci hissə n / 2 üst kartlardan, ikinci hissə isə n / 2 alt kartlardan ibarətdir. Daha sonra, nəticə dəstəsi hər iki hissədən növbə ilə bir kart götürülərək formalaşdırılır, birincidən başlayaraq. D çevrilməsi isə yalnız ikinci addımda fərqlənir: nəticə dəstəsi ikinci hissədən başlayaraq formalaşdırılır.
Əgər kartları yuxarıdan aşağıya doğru 1, 2, ..., n rəqəmləri ilə nömrələsək, U çevrilməsinin nəticəsində kartlar yuxarıdan aşağıya doğru 1, n / 2 + 1, 2, n / 2 + 2, ..., n / 2, n ardıcıllığında olacaq. D çevrilməsinin nəticəsində isə kartların ardıcıllığı belə olacaq: n / 2 + 1, 1, n / 2 + 2, 2, ..., n, n / 2.
Sergey Mixayloviç testləri belə aparır: O, 1-dən n-ə qədər nömrələnmiş n kart götürür və kartların nömrələri yuxarıdan aşağıya doğru artan şəkildə dəstə təşkil edir. Sonra o, dəstəni maşına yerləşdirir və qarışdırma aparır. Bundan sonra Sergey Mixayloviç nəticə dəstəsindən yuxarıdan k-cı kartı çıxarır və onun nömrəsinə görə test olunan maşının işlək və ya nasaz olması barədə nəticə çıxarır.
Test prosesini sürətləndirmək üçün Sergey Mixayloviçə bir proqram lazımdır ki, əgər şaffl-maşın düzgün işləyirsə, nəticə dəstəsində yuxarıdan k-cı kartın nömrəsini hesablaya bilsin.
Giriş məlumatları
Birinci sətir n və k tam ədədlərini (1 ≤ k ≤ n ≤ 2 * 10^9, n cüt ədəddir) ehtiva edir. İkinci sətirdə 1-dən 1000-ə qədər 'U' və 'D' simvolları boşluqsuz yazılıb. Bu simvollar kartların yerini dəyişmək üçün maşın tərəfindən tətbiq olunan çevrilmə ardıcıllığını təsvir edir. 'U' simvolu U çevrilməsinə, 'D' simvolu isə D çevrilməsinə uyğundur.
Çıxış məlumatları
Bir tam ədəd - nəticə dəstəsində yuxarıdan k-cı kartın nömrəsini, birdən başlayaraq, çıxarın.