Chữ số thứ K

Trong khi bạn bè cùng trang lứa đang đi chơi Halloween, Bob quyết định ở nhà chăm chỉ giải các bài tập được giao để trở nên thật xuất sắc trong lớp và có cơ hội giành học bổng. Trong quá trình luyện tập, Bob gặp phải một bài toán hóc búa. Biết bạn là một lập trình viên tài năng và giàu kinh nghiệm, Bob đã gửi tín hiệu cầu cứu đến bạn. Hãy giúp Bob giải quyết bài toán này nhé!

Đề bài như sau: Bob có 2 số l, r. Nhiệm vụ của Bob là tìm chữ số thứ k tính từ trái sang phải sau khi tính tổng tất cả các số từ l đến r.

Đầu vào: Một dòng duy nhất chứa 3 số $l, r, k$, trong đó $[l, r]$ là khoảng cần tính tổng và k là vị trí của chữ số cần tìm sau khi tính tổng ($1\leq l \leq r \leq 5.10^8$, $1 \leq k \leq len(s)$, với $s$ là tổng của các số từ l đến r).

Đầu ra: In ra một dòng duy nhất chứa chữ số thứ k của tổng tất cả các giá trị từ l đến r.

Giải thích: Tổng các số từ $4 \to 100$ là $5044$. Do đó, chữ số thứ 2 của 5044 là 0.

Ví dụ 1:

Đầu vào:

4 100 2

Đầu ra:

0