Algorithm

E2. Numerical Sequence (hard version)
time limit per test
2 seconds
memory limit per test
256 megabytes
Problem link- https://codeforces.com/contest/1216/problem/E2
input
standard input
output
standard output

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……" which consist of blocks of all consecutive positive integers written one after another. The first block consists of all numbers from 11 to 11, the second one — from 11 to 22, the third one — from 11 to 33, ……, the i�-th block consists of all numbers from 11 to i�.

So the first 5656 elements of the sequence are "11212312341234512345612345671234567812345678912345678910". Elements of the sequence are numbered from one. For example, the 11-st element of the sequence is 11, the 33-rd element of the sequence is 22, the 2020-th element of the sequence is 55, the 3838-th element is 22, the 5656-th element of the sequence is 00.

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

Input

The first line of the input contains one integer q� (1≤q≤5001≤�≤500) — the number of queries.

The i�-th of the following q� lines contains one integer ki�� (1≤ki≤1018)(1≤��≤1018) — the description of the corresponding query.

Output

Print q� lines. In the i�-th line print one digit xi�� (0≤xi≤9)(0≤��≤9) — the answer to the query i�, i.e. xi�� should be equal to the element at the position ki�� of the sequence.

Examples
input
Copy
5
1
3
20
38
56
output
Copy
1
2
5
2
0
input
Copy
4
2132
506
999999999999999999
1000000000000000000
output
Copy
8
2
4
1
Note

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

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

int q;

long long digits_until_block(long long block) {
	long long tot = 0, sub = 0;
	while(sub < block) {
		tot += (block - sub) * (block + 1 - sub) / 2.0;
		sub *= 10, sub += 9;
	}
	return tot;
}

long long get_block(long long n) {
	long long l = 1, r = 1e9, mid, res;

	while(l <= r) {
		mid = (l + r) / 2;

		if(digits_until_block(mid) >= n && digits_until_block(mid - 1) < n) {
			res = mid;
			break;
		} else if(digits_until_block(mid) < n)
			l = mid + 1;
		else
			r = mid - 1;
	}

	return res;
}

long long digits_until_number(long long number) {
	long long tot = 0, sub = 0;
	while(sub < number) {
		tot += (number - sub);
		sub *= 10;
		sub += 9;
	}
	return tot;
}

long long get_number(long long n, long long block) {
	long long l = 1, r = 1e9, mid, res;

	while(l <= r) {
		mid = (l + r) / 2;

		if(digits_until_number(mid)>= n && digits_until_number(mid - 1) < n) {
			res = mid;
			break;
		} else if(digits_until_number(mid) < n)
			l = mid + 1;
		else
			r = mid - 1;
	}

	return res;
}

long long get_digit(long long n, long long i) {
	long long nrev = 0;
	while(n != 0) {
		nrev *= 10;
		nrev += (n % 10);
		n /= 10;
	}
	long long cnt = 0, cur = 0;
	while(cnt != i) {
		cur = nrev % 10;
		nrev /= 10;
		cnt += 1;
	}

	return cur;
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in", "r", stdin);
#endif

	scanf("%d", &q);
	for(int i = 0; i < q; ++i) {
		long long tmp;
		scanf("%lld", &tmp);
		long long block = get_block(tmp);
		tmp -= digits_until_block(block - 1);
		long long number = get_number(tmp, block);
		tmp -= digits_until_number(number - 1);
		printf("%lld\n", get_digit(number, tmp)>;
	}

	return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
5
1
3
20
38
56

Output

x
–
+
cmd
1
2
5
2
0
Advertisements

Demonstration

Codeforcess Solution E2. Numerical Sequence (hard version)-Solution in C, C++, Java, Python,Codeforcess Solution

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+