On a warm summer's day, brothers Ohani and Inaho are playing legos with each other. Out of nowhere, Ohani mentions his encounter with a golden porcupine earlier this morning. Excited, Inaho then makes a blood pact with his brother to solve the golden porcupine's riddles by tonight, both brothers love computer science.

Inaho grabs his metal detector and enters the magical forest to search for the golden porcupine. He searches for 2 ~(2 \le 2 \le 2)~ minutes but finds nothing and gives up. Absolutely devastated, Inaho returns home to a golden porcupine on his front lawn.

The porcupine then begins to shoot his quills and begs Inaho for the total height at every second of time with a high pitch that if for not thy soul's gate t'was reinforced twice through mythril, whos angel's wings depen'd for lightness and flight, for strength and cease of blight, would shatter Inaho's meek gate, damned to hades. Inaho, remembering he missed KurbyDoo prefix sum array lesson, cries as he cannot solve the golden porcupine's riddles. One of the quills hits Inaho's head and he falls unconscious.

Waking up, the porcupine is long gone. Furious at himself, Inaho screams "If only there was a problem involving PSA's that is so conveniently similar but is everslightly easier to complete where upon completion, would provide the perfect stepping stone to complete the golden porcupine's riddle."

"Hey, are you okay?" says a reassuring voice. "Its me, Silver the hedgehog from Sega's Sonic the Hedgehog ©Sega, 2006." Inaho, still crying, replies "Thank you kind sir, but why would you help me?"

Silver the hedgehog smiles and says:

Over a period of ~T~ seconds, I will shoot ~N~ quills out in total. For the ~i^{th}~ quill, it only exists from second ~S_i~ to ~T~ (inclusive).

Since my quills are magical and are not affected by gravity, the height of the ~i^{th}~ can be expressed as ~a_ix + b_i~ where ~a_i~ and ~b_i~ are constants for the ~i^{th}~ quill and ~x~ is the number of seconds the quill has been in the air. For the ~i^{th}~ quill, at time ~S_i~, ~x~=0.

Unlike my good friend the golden porcupine, my quills do not have the same intangible properties he does. Any quill that touches the ground or goes below it ~(f(x) \le 0)~ ceases to exist from that point forward. This is still true for quills that originate underneath the ground.

Can you solve my ~Q~ queries? Each query will be given a range from ~L_i~ to ~R_i~. For each quill, get the sum of the quill's height at each second between ~L_i~ and ~R_i~ inclusive. If at that point the quill doesn't exist, consider its height to be 0. Then get all of the sums for each quill and add them together, that is what you need to give me.

Inaho replies "This is impossible! my head can't hold all that information." Silver answers Inaho with a soft voice:

Your memory is overflowing, use a 64-bit data type such as long long

Inaho completes Silver's riddle and feels euphoric, excited to find and complete the golden porcupine's riddle tomorrow. He wearily goes inside, oblivious of his imminent death from his failure to complete the blood pack.

Can you complete Silver's problem?

Input Specification

The first line will contain two integers, ~N~, ~T~ ~(1 \le N \le 10^5, 1 \le T \le 10^5)~.

The next ~N~ lines will contain three integers, ~A_i~ ~(-10^3 \le A_i \le 10^3)~, ~B_i~ ~(-10^3 \le B_i \le 10^3)~, and ~S_i~ ~(1 \le S_i \le T)~ representing the constraints of quill ~i~.

The next line will contain integer ~Q~ ~(1 \le Q \le 10^3)~

The next ~Q~ lines will contains two integers, ~L_i~ and ~R_i~ ~(1 \le L_i \le R_i \le T)~.

Output Specification

Print ~Q~ lines containing one integer representing the sum of the total heights of all applicable quills of each second from ~L_i~ to ~R_i~ inclusive.

Subtasks

Subtask 1 [30%]:

• ~N, Q, A_i \le 10~
• ~T, B_i \le 100~

Subtask 2 [70%]:

• No further constraints

Sample Input 1

2 7
1 1 1
-1 2 3
1
1 7

Sample Output 1

31

Explanation For Sample Output 1

The trajectories of the quills are represented in a graph below (note: the x value represents the quill's time since existence starting at second 1).

The 1st and only query is from seconds 1 to 7
At the 1st second, the total height is 1 as the second quill doesn't exist (1)
At the 2nd second, the total height is 2 as the second quill doesn't exist (2)
At the 3rd second, the total height is 5 (3 + 2 = 5)
At the 4th second, the total height is 5 (4 + 1 = 5)
At the 5th second, the total height is 5. From this point forward the 2nd quill ceases to exist (5 + 0 = 5)
At the 6th second, the total height is 6 as the second quill doesn't exist (6)
At the 7th second, the total height is 7 as the second quill doesn't exist (7)

Sample Input 2

3 21
1 4 5
-7 21 2
-100000 -10000 1
2
9 19
1 13

Sample Output 2

143
114