410783: GYM104103 D The Name of the Fourth Problem

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

D. The Name of the Fourth Problemtime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

Consider an infinite sequence of integers $$$a_1, a_2, a_3, \ldots$$$. The sequence is called a self-describing if $$$a_i$$$ is equal to the number of occurrences of $$$i$$$ in this sequence.

If we restrict this sequence to satisfy $$$a_1 = 1$$$ and the numbers a non-decreasing (that is, $$$a_i \le a_{i+1}$$$ for all $$$i$$$), then the self-describing sequence is unique. The first thirty elements are as follows:

$$$$$$ 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, \ldots $$$$$$

Your task is to calculate the range sum queries for this sequence efficiently. Let's go!

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of range sum queries. The following $$$t$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le 10^{15}$$$) each. The $$$i$$$-th query requires you to calculate $$$\sum_{k=l_i}^{r_i} a_k$$$.

Output

Print $$$t$$$ lines, each one with a single integer — the answer to the range sum query. Because the sum can be large, print it modulo $$$1\,000\,000\,007$$$.

Scoring
SubtaskPointsConstraints
112$$$l_i = r_i$$$; $$$r_i \le 1000$$$
27$$$l_i = r_i$$$; $$$r_i \le 10^6$$$
38$$$r_i \le 10^6$$$
430$$$r_i \le 10^{10}$$$
543No additional constraints
ExampleInput
5
1 1
2 2
3 4
56 56
5 13
Output
1
2
5
14
42

加入题单

上一题 下一题 算法标签: