Chef and Magic Numbers
All submissions for this problem are available.
Chef is the cleverest man in the whole world. However he is not interested in science, give him the magic. His first magic lesson consists of converting a number k to F(k) where F(k) - is the k-th magic integer. An integer is magic if S(n) is smaller than or equal to q. S(n) is the sum of squares of the digits in n. For example, S(13) = 1^2 + 3^2 = 10.
Now Chef want to test his magical abilities. He knows how to solve this task, but who will check it? That is where you come in.
The problem is as follows: there is an array of N numbers. Let A be the given array. Then Bi = F(Ai) for all i (1 <= i <= N). This is followed by M queries of the form (l, r). For each such query you need to find the sum of the elements of the array B that are in the interval (l, r) modulo 1000000007.
InputThe first line of the input contains an integer q. The next line contains an integer N. The third line contains N space-separated integers A1, A2, ..., AN denoting the given array. Next line contains M denoting the number of queries. The next M lines contains two integers denoting left and right ends of queries.
OutputFor each query, output a single line containing sum of the elements of the array B in the given interval.
- 1 ≤ q ≤ 10^9
- 1 ≤ N ≤ 3*10^5
- 1 ≤ Ai ≤ 3*10^5
- 1 ≤ M ≤ 10^5
- 1 ≤ l ≤ r ≤ N
Input: 201 5 1 2 10 5 10000 5 1 1 2 2 3 3 5 5 1 5 Output: 1 2 10 10636 10654
ScoringSubtask 1 (30 points): 200 ≤ q ≤ 109.
Subtask 2 (70 points): Look at constraints
|Tags||ad-hoc, furko, ltime04, medium|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.