CF1177B Digits Sequence (Hard Edition)

让我们将所有正整数依次写在一起，从 $1$ 开始，没有任何分隔符（即作为一个单独的字符串）。这将是以 $123456789101112131415161718192021222324252627282930313233343536...$ 为开头的无穷序列，现在你要输出它的第 $k$ 项。

输入一个整数 $k~(k \le 10^{12})$。

输出第 $k$ 项的值。