1216E2 · Numerical Sequence (hard version)

Problem: The only difference between the easy and the hard versions is the maximum value of $k$.

You are given an infinite sequence of form "112123123412345$\dots$" which consist of blocks of all consecutive positive integers written one after another. The first block consists of all numbers from $1$ to $1$, the second one — from $1$ to $2$, the third one — from $1$ to $3$, $\dots$, the $i$-th block consists of all numbers from $1$ to $i$.

So the first $56$ elements of the sequence are "11212312341234512345612345671234567812345678912345678910". Elements of the sequence are numbered from one. For example, the $1$-st element of the sequence is $1$, the $3$-rd element of the sequence is $2$, the $20$-th element of the sequence is $5$, the $38$-th element is $2$, the $56$-th element of the sequence is $0$.

Your task is to answer $q$ independent queries. In the $i$-th query you are given one integer $k_i$. Calculate the digit at the position $k_i$ of the sequence.

Input Format: The first line of the input contains one integer $q$ ($1 \le q \le 500$) — the number of queries.

The $i$-th of the following $q$ lines contains one integer $k_i$ $(1 \le k_i \le 10^{18})$ — the description of the corresponding query.

Output Format: Print $q$ lines. In the $i$-th line print one digit $x_i$ $(0 \le x_i \le 9)$ — the answer to the query $i$, i.e. $x_i$ should be equal to the element at the position $k_i$ of the sequence.

Note: Answers on queries from the first example are described in the problem statement.