Chữ số thứ k

Viết tất cả các số nguyên dương lên một hàng theo thứ tự tăng dần, ta được một dãy chữ số vô hạn:

1234567891011121314...

Cho số nguyên \(k\), hãy tìm chữ số thứ \(k\) trong dãy chữ số nói trên.

Input

Một dòng duy nhất chứa số nguyên \(k\) (\(1 \le k \le 10^{18}\)).

Output

In ra một chữ số duy nhất - chữ số thứ \(k\) của dãy.

Example

Input:

14

Output:

1

Note

Dãy chữ số được ghép từ các số \(1, 2, 3, \ldots\): "\(1\) \(2\) \(3\) \(4\) \(5\) \(6\) \(7\) \(8\) \(9\) \(10\) \(11\) \(12\) \(13\) \(14\) \(\ldots\)" tương ứng với dãy chữ số "1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 1 4...". Chữ số ở vị trí thứ \(14\) (tính từ \(1\)) là chữ số đầu tiên của số \(12\), tức là chữ số "1".