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.