Ito

Math can be very interesting and fascinating, and it is no doubt worth a lifetime. But if you plan to spend your last days somewhere in the Caribbean, feeling warm sand under your feet and watching beautiful women bring you pina coladas one by one, you should find another use for your skills.

So Kiyoshi decided that his contribution to math was already great enough, and he would go make some money. As you have probably heard, an economic crisis is approaching quickly, and everyone wants an efficient way to save money. To follow the new market trends, Kiyoshi opened a consulting agency that helps clients invest their savings properly. Investment here has three simple steps: go to the market and buy some valuables, wait a year, then go back to the market and sell them.

There are $N$ different valuables available for investment. For each one, the current price $c_i$ wooddollars per measure unit is given. All valuables are unlimited in quantity and arbitrarily divisible, so you may buy any non-negative real amount of any valuable. For each valuable, two limits $a_i$ and $b_i$ are known. Next year, the cost of one measure unit will be continuously and uniformly distributed between these two values.

$M$ clients want Kiyoshi to create a good investment plan for each of them. The $i$-th client has $s_i$ wooddollars. On one hand, each client wants to maximize the expected amount of money they will have after selling all valuables. On the other hand, they fear losing too much, so they want at least $l_i$ wooddollars in the worst case.

For each client, Kiyoshi needs to choose how much of each valuable the client should buy. The client can spend any amount of wooddollars, but no more than they own. Any unspent money is kept until next year. Tell each client the maximum expected sum of wooddollars they could have without risking too much.

The first line contains two integers $N$ and $M$ ($0 \leq N, M \leq 100000$), the number of valuables and the number of clients.

The next $N$ lines describe the valuables. Each contains three integers $c_i$, $a_i$, and $b_i$: the current cost of the valuable, and the limits $a_i$ and $b_i$ on its future cost ($1 \leq c_i \leq 100000$, $0 \leq a_i \leq b_i \leq 100000$).

Then $M$ lines describe the clients. Each contains two integers $s_i$ and $l_i$: the amount of money the client has, and the minimum amount the client accepts in the worst case ($1 \leq l_i \leq s_i \leq 100000$).

Print $M$ lines. The $i$-th line contains one real number: the maximum expected amount of wooddollars the $i$-th client could have without risking too much. An answer is accepted if its absolute or relative error does not exceed $10^{-6}$. Formally, if your answer is $A$ and the jury's answer is $B$, the checker accepts it when $\frac{|A-B|}{\max(1,B)} \leq 10^{-6}$.

In the example above, the first client buys $0.1$ units of the second valuable and $9$ units of the third. The second client buys $0.4$ units of the first valuable, $0.3$ units of the second, and $3$ units of the third. The third client buys just $1$ unit of the second valuable.