Nam là một học sinh rất thích sáng tạo trong việc học môn Toán. Khi học về bài dãy số, 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, \dots~

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 lớp 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".

Bạn hãy giúp Nam lập trình giải bài toán này nhé.

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~ ~(a_0\le 10^{10^5})~.
• 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 ra 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

• Subtask 1: ~60\%~ test có ~N \le 20~;
• Subtask 2: ~40\%~ test không có ràng buộc gì thêm.