LIFERACE - LIFE IS A RACE

Life is a race with hard working humans. Assume a hypothetical situation in which God has to send many humans on earth with some level of intelligence. Level of intelligence is measured in a whole number. God has to take care that person arriving later on earth should have more level of intelligence so as to cope with the competitive world. God’s assistant suggested him a non-decreasing sequence called S. Lets see the sequence.

Description of Sequence

Any natural number n occurs exactly S[n] times and all n occurs consecutively. The first few terms are stated below.

n 1 2 3 4 5 6 7 8 9 10 11 12 ...

S(n) 1 2 2 3 3 4 4 4 5 5 5 6 ...

S[1000] = 86

So, Person 1 arrives on earth with level of intelligence = 1.

Person 2 arrives on earth with level of intelligence = 2.

Person 3 arrives on earth with level of intelligence = 2.

Person 4 arrives on earth with level of intelligence = 3.

And so on.

But God sends some good hearted person (Person who not only lives for themselves but for the world) when n's cube root is a positive integer. But there is a SuperGod which rarely opens his eyes and as he opens his eyes, he increases the level of intelligence of some of the good hearted persons. Now God needs to know the total level of intelligence of some of the good hearted people.

Good hearted person 1: person 1

Good hearted person 2: person 8

Good hearted person 3: person 27

Good hearted person 4: person 64

And so on.

God needs a programmer to solve his queries. God’s input data format is explained below.

Will You help God?? (He might increase your lifetime :) )

Input

First line of input contains 2 integers, x and y, where x denotes the number of time the SuperGod opened his eyes and y denotes the number of queries of God.

Next x lines follows 3 integers L, R, I, which denote that SuperGod has increased the level of intelligence of good hearted people ranging between L and R (inclusive both) by a constant I.

Next y lines follows 2 integers L, R, which denotes that God needs to know the total level of intelligence of good hearted persons ranging between L and R (both inclusive).

Note:

Good hearted person L is person L*L*L.

Good hearted person L+1 is person (L+1)*(L+1)*(L+1)

Good hearted person R is person R*R*R.

Output

Output should contain exactly y lines, each containing the answer.

Example

Input:
1 1
1 1 1
1 2

Output:
6

Explanation of Example

Answer is S[1] + S[2*2*2] + 1 = 6

Constraints

x <= 100000

y <= 100000

1 <= L, R <= 999999

I <= 10

Click here to see my set of problems at Spoj.


Added by:devu
Date:2013-03-18
Time limit:1s
Source limit:5000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem.

hide comments
2013-09-04 04:44:25 যোবায়ের
It makes a very little difference if you describe how S[n] progresses, because people will get that from OEIS anyway. So hiding those details doesn't necessarily make this problem special.
Note: Test data contains L > R

Last edit: 2013-04-03 00:50:01
2013-09-04 04:44:25 Francky
I don't understand well the question, but is it very different from the classical SEQ7 ? If no, this problem will be moved.
edit : and there's yet an easy edition with MAIN12A.
RE: SEQ7 asks only upto 1e13 and my problem is asking users to calculate up to 999999^3 . The Problem does not only asks for Sequence ...It asks more than only solving for Sequence and second problem is totally different from my problem.
--ans(francky)--> But here is with Cube cluster and SEQ7 on Pyramid ; the awaited complexity seems the same, isn't it ?
RE: I think You need to work out more in this problem in comparison to that one.Let People Comment if they still want it to be tutorial ,i have no Objection.

Last edit: 2013-03-27 15:22:55
2013-09-04 04:44:25 devu
@RAJDEEP GUPTA: n occurs S[n] Times as mentioned in the problem statement
RE(Ikhaduri) His question was how should we count S[n], not what S[n] means.
RE: If it is so, then I am Sorry ... I won't destroy my problem :)

Last edit: 2013-03-26 09:28:26
2013-09-04 04:44:25 RAJDEEP GUPTA
I could not understand how S[n] progresses. Are we supposed to infer it ourselves?
2013-09-04 04:44:25 mala da.... annamala
Can i get some more test cases
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.