Chữ số

Trong buổi giao lưu giữa 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à số 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. Khi viết ngược, mọi chữ số đều được giữ lại, kể cả các chữ số $0$ (chẳng hạn $a_0=120$ thì $a_1=120021$).

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". 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$ (tính từ trái sang, bắt đầu từ $1$) của số hạng $a_N$.

Dữ liệu vào

• Dòng đầu ghi số tự nhiên $a_0$ (không có chữ số $0$ ở đầu).
• 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.

Dữ liệu ra

In ra chữ số tìm được. Trong trường hợp không tìm được chữ số nào (số hạng $a_N$ có ít hơn $K$ chữ số) thì in ra $-1$.

Ràng buộc

• $1\le a_0<{10}^{10}$.
• $1\le N\le 63$.
• $1\le K\le {10}^{18}$.

Subtasks

• Có $60\%$ số test ứng với $60\%$ số điểm có $N\le 20$.
• Có $40\%$ số test còn lại không có ràng buộc gì thêm.

Ví dụ