Trong buổi giao lưu giữa các các bạn đội tuyển môn Tin học tại Trại hè Hùng Vương lần thứ X, được tổ chức tại Trường THPT chuyên Hạ Long, Nam nghĩ ra một dãy số (~a_n~) mà cậu ta gọi là dãy đặc biệt được xây dựng theo quy tắc sau:

• Cho trước số ~a_0~ là số tự nhiên có tối đa 10 chữ số.
• Số ~a_i~ (~i \ge 1~) là một số tự nhiên nhận được từ ~a_{i-1}~ bằng cách viết thêm vào sau các chữ số của ~a_{i-1}~ chính ~a_{i-1}~ nhưng viết theo thứ tự ngược lại.

Chẳng hạn: ~a_0 = 345, a_1 = 345543, a_2 = 345543345543, ...~

Nam rất thích dãy số này và đem khoe nó với các bạn. Hoàng là một thành viên trong đội cảm thấy thích thú với dãy số đặc biệt này. Sau một lúc suy nghĩ, Hoàng liền đố Nam một bài toán sau: "Với hai số nguyên dương ~N~ và ~K~ cho trước, hãy tìm chữ số thứ ~K~ của số hạng ~a_N~ trong dãy đặc biệt trên".

Yêu cầu: Cho trước ~a_0, N~ và ~K~. Hãy tìm chữ số thứ ~K~ của số hạng ~a_N~.

Input

• Dòng đầu ghi số tự nhiên ~a_0~.
• Dòng thứ hai ghi hai số nguyên dương ~N, K~ (~1 \le N \le 63, 1 \le K \le 10^{18}~). Các số cách nhau ít nhất một dấu cách.

Output

• Ghi chữ số tìm được. Trong trường hợp không tìm được chữ số nào thì ghi ra -1.

Sample Input 1

345
2 10

Sample Output 1

5

Subtasks