C. Supply and Demand
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

With Valentine's Day coming around, Magikarp smells a great business opportunity to sell chocolates. Magikarp owns $$$n$$$ different shops, each labeled from $$$1,2,\ldots,n$$$, each of which has a different consumer base and cost structure. He wonders what the maximum profit he can make is if he must set the same price for his chocolate at every one of his stores. Using magik, Magikarp knows that if he sets a price of $$$p$$$ dollars, the $$$i^\text{th}$$$ shop will sell $$$a_i - b_i \cdot p$$$ chocolates. He also knows that each chocolate produced in the $$$i^\text{th}$$$ shop costs $$$c_i$$$ dollars.

Magikarp wants to take a contiguous subarray of his shops to produce chocolates, shutting down all the other stores in the meantime. Given $$$q$$$ queries of the form $$$(l_j,r_j)$$$, find the maximum profit Magikarp can make if he only opens shops with numbers from $$$l_j$$$ to $$$r_j$$$, inclusive, and he must set his price to be a whole number of dollars in the range $$$[0,m]$$$. Note that there can be cases where Magikarp loses money no matter what price he uses.

$$$^\dagger$$$You can assume that all shops will sell a non-negative number of chocolates for all possible prices in the range $$$[0,m]$$$.

Input

The first line of input contains $$$n$$$, $$$m$$$, and $$$q$$$ $$$(1\le n,m,q\le 2\cdot 10^5)$$$ — the number of shops, the maximum possible price, and the number of queries

The $$$i^\text{th}$$$ of the next $$$n$$$ lines contain 3 space-seperated integers, $$$a_i$$$, $$$b_i$$$, and $$$c_i$$$ $$$(0\le a_i,b_i,c_i\le 10^6)$$$

The $$$j^\text{th}$$$ of the next $$$q$$$ lines contain $$$l_j$$$ and $$$r_j$$$ $$$(1\le l_j\le r_j\le n)$$$ — the left and right index of the $$$j^\text{th}$$$ query

Output

Print out $$$q$$$ lines, each containing a single integer answering the $$$j^\text{th}$$$ query.

Example
Input
5 10 5
50 5 0
90 9 1
100 1 8
60 6 6
80 8 0
1 5
1 2
2 5
3 3
5 5
Output
360
305
278
180
200