数学是非常有趣且迷人的，毫无疑问，它值得人们为之奉献一生。然而，如果你计划在加勒比海的某个地方度过余生，感受脚下的暖沙，看着美女们一个接一个地送来 Pina Colada，你真的应该为你的技能寻找另一种应用。

这就是为什么 Kiyoshi 认为他在数学上的贡献已经足够大了，所以他可以去赚点钱。正如你可能听说的那样，经济危机即将来临，每个人都在关心如何有效地储蓄资金。为了紧跟新的市场趋势，Kiyoshi 开了一家咨询公司，帮助客户妥善投资他们的积蓄。本题中的投资过程包含三个简单的步骤：去市场购买一些有价证券，等待一年，然后再次去市场卖出这些证券。

市场上有 $N$ 种不同的有价证券可供投资。对于每种证券，已知其当前价格为每单位 $c_i$ 木元（wooddollars）。你可以假设所有证券的数量都是无限的且可任意分割，即可以购买任意非负实数单位的任何证券。此外，对于每种证券，已知两个限制 $a_i$ 和 $b_i$，确定了明年每单位证券的价格将在这些值之间连续且均匀地分布。

有 $M$ 位客户希望 Kiyoshi 为他们制定一份好的投资计划。第 $i$ 位客户拥有 $s_i$ 木元。一方面，每位客户都希望最大化他在卖出所有证券后所拥有的预期金额。另一方面，他们害怕损失太多，因此他们希望在最坏的情况下至少拥有 $l_i$ 木元。

对于每位客户，Kiyoshi 需要选择客户应该购买多少每种证券。客户可以花费任意金额的木元，但不能超过他拥有的金额。当然，他明年将拥有所有未花费的钱。

数据量太大，所以 Kiyoshi 请求你的帮助。请告诉每位客户在不承担过多风险的情况下，他可能拥有的最大预期木元总额。

输入格式

第一行包含两个整数 $N$ 和 $M$ ($0 \le N, M \le 100\,000$)，分别表示可用的证券数量和客户数量。

接下来的 $N$ 行描述了市场上可购买的证券。每行包含三个整数 $c_i, a_i$ 和 $b_i$，分别表示该证券的当前成本以及未来成本的限制 $a_i$ 和 $b_i$ ($1 \le c_i \le 100\,000, 0 \le a_i \le b_i \le 100\,000$)。

随后是 $M$ 行，描述了 Kiyoshi 的客户。对于每位客户，给出整数 $s_i$ 和 $l_i$ —— 他拥有的金额以及他在最坏情况下能接受的最低金额 ($1 \le l_i \le s_i \le 100\,000$)。

输出格式

输出 $M$ 行，第 $i$ 行包含一个实数 —— 第 $i$ 位客户在不承担过多风险的情况下可能拥有的最大预期木元总额。如果你的答案的绝对误差或相对误差不超过 $10^{-6}$，则你的答案将被视为正确。

形式上，如果你的答案是 $A$，评测系统的答案是 $B$，则当 $\frac{|A-B|}{\max(1, B)} \le 10^{-6}$ 时，评测系统将接受你的答案。

样例

输入 1

3 3
10 5 31
10 10 12
10 5
10 1
10 5
10 10

输出 1

23.6000000000
18.0000000000
11.0000000000

说明

在上面的例子中，第一位客户可以购买 0.1 单位的第二种证券和 9 单位的第三种证券。

第二位客户可以购买 0.4 单位的第一种证券、0.3 单位的第二种证券和 3 单位的第三种证券。

第三位客户只能购买 1 单位的第二种证券。