Đàn bò đang thử nghiệm các mật mã bí mật và đã nghĩ ra một phương pháp tạo một xâu dài vô hạn để dùng làm một phần trong mật mã của chúng.

Với một xâu \(s\), gọi \(F(s)\) là xâu \(s\) nối với xâu \(s\) được "xoay" sang phải một ký tự (khi xoay phải, ký tự cuối của \(s\) vòng lại và trở thành ký tự đầu tiên mới). Từ xâu ban đầu \(s\), đàn bò xây dựng xâu mật mã dài vô hạn bằng cách áp dụng \(F\) lặp đi lặp lại; vì vậy, sau mỗi bước, độ dài của xâu hiện tại tăng gấp đôi.

Cho xâu ban đầu và một chỉ số \(N\), hãy giúp đàn bò tính ký tự ở vị trí thứ \(N\) trong xâu mật mã vô hạn.

Dữ liệu vào

Dữ liệu vào gồm một dòng duy nhất chứa một xâu, theo sau là \(N\). Xâu gồm không quá \(30\) chữ cái in hoa và \(N \leq 10^{18}\).

Lưu ý rằng \(N\) có thể quá lớn để lưu trong một số nguyên \(32\) bit tiêu chuẩn, vì vậy bạn có thể cần dùng kiểu số nguyên \(64\) bit (chẳng hạn long long trong C/C++).

Dữ liệu ra

In ký tự thứ \(N\) của xâu mật mã vô hạn được xây dựng từ xâu ban đầu. Ký tự đầu tiên ứng với \(N=1\).

Ví dụ

COW 8

C

COW -> COWWCO -> COWWCOOCOWWC
                 12345678

Nguồn

USACO 2017 January Contest, Silver — Secret Cow Code. Tác giả đề: Brian Dean.

https://usaco.org/index.php?page=viewproblem2&cpid=692