测试数据来自 system/1678

背景

陶陶很喜欢做白日梦。

描述

有一天，陶陶梦见他来到了一个遍地黄金的地方。不过奇怪的是这些黄金都排成了一条直线。

正当陶陶欢喜且纳闷的时候，curimit出现了！curimit说："你想不想取走这些黄金？"陶陶说："嗯~~。" curimit说："你只要回答我Q个问题，如果你都回答对了，那么这些黄金都归你。首先，我告诉你第i块黄金的体积v[i]和价值e[i]。然后，我问你Q个问题，每个问题都是询问：如果你有一个大小为V的背包，并且只允许你带走编号从l到r的黄金，那么你最多能带走多少价值的黄金。"陶陶听后立刻晕了过去，醒来之后陶陶第一个想到的就是你，他想要你帮他来回答这Q个问题，并且答应你事成之后，与你0：0平分掉这些黄金（因为在做白日梦）。

注：黄金是可以分割的，即你可以取走一块黄金的3/5，这样的话，3/5块黄金的体积和价值都是原来的3/5。

格式

输入格式

输入文件的第一行为两个整数n，Q分别表示一共有n块黄金，一共有Q次询问。

第二行有n个整数，第i个整数表示第i块黄金的价值大小。

第三行有n个整数，第i个整数表示第i块黄金的体积大小。

第四行开始到第n+3行，第i+3行有三个数，l，r，V，表示询问如果只允许取走编号从l到r的黄金，且你的背包大小为V，你最多能带走多少价值的黄金。

输出格式

输出文件仅包含一行，Q个实数表示Q次询问的答案，每个实数保留2位有效数字，相邻两个数之间用空格隔开，行末回车。

样例1

样例输入1

3 2
2 3 4
4 5 6
1 2 9
2 3 8

样例输出1

5.00 5.20

限制

2秒

提示

【样例解释】
第一次询问：取走编号1和编号2的两块黄金，总体积9，总价值5.00
第二次询问：取走编号3的黄金和编号为2的黄金的2/5，总体积8，总价值5.20

【提醒】
由于精度误差，0.00499999999999可能会四舍五入成0.00，而正确答案应该是0.01。

【约定】
对于30%的数据， n≤1000 Q≤1000
对于50%的数据， n≤50000 Q≤10000
对于100%的数据，n≤100000 Q≤100000

来源

原创题。