Viết tất cả các số nguyên dương theo thứ tự tăng dần thành một hàng như sau:

1234567891011121314...

Hỏi chữ số thứ ~k~ là chữ số nào?

Dữ liệu vào

Dòng đầu tiên và duy nhất chứa một số nguyên ~k~.

Kết quả

In ra chữ số thứ ~k~.

Ví dụ

Đầu vào:

14

Đầu ra:

1

Giải thích: Chín vị trí đầu tiên là các số ~1~ đến ~9~. Sau đó số ~10~ chiếm vị trí ~10~ và ~11~, số ~11~ chiếm vị trí ~12~ và ~13~, số ~12~ chiếm vị trí ~14~ và ~15~. Vậy chữ số thứ ~14~ là chữ số đầu tiên của ~12~, tức là ~1~.

Giới hạn

• ~1 \le k \le 10^{18}~

Các số có ~d~ chữ số gồm ~9 \cdot 10^{d-1}~ số và đóng góp ~9 \cdot 10^{d-1} \cdot d~ chữ số. Với ~d = 18~ tích này vượt quá phạm vi số nguyên có dấu 64 bit, hãy cẩn thận khi cộng dồn.