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]$$$.
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
Print out $$$q$$$ lines, each containing a single integer answering the $$$j^\text{th}$$$ query.
5 10 550 5 090 9 1100 1 860 6 680 8 01 51 22 53 35 5
360 305 278 180 200
