题目描述

Peter 最近开始把调配软饮料当作一项业余爱好。他购买了 $N$ 种不同饮料的无限供应权限。

第 $i$ 种饮料（$0 \le i < N$）每升含有：

• $A_i$ 克糖；
• $B_i$ 克酸。

Peter 邀请了 $Q$ 位朋友来家里做客。每位朋友都很注重健康，并且对饮料有如下要求：

• $M_A$：最多愿意摄入的糖总量（克）；
• $M_B$：最多愿意摄入的酸总量（克）；
• $L_A, R_A$：Peter 只能选用每升含糖量 $A_i$ 落在区间 $[L_A, R_A]$ 内的饮料来为该朋友调配饮料。

Peter 可以将若干种饮料按任意非负实数体积混合（允许使用小数升数）。

设第 $i$ 种饮料在最终混合饮料中使用了 $V_i$ 升，则：

• 总体积为

$$\sum_{i=0}^{N-1} V_i$$

• 总糖含量为

$$\sum_{i=0}^{N-1} V_i \cdot A_i$$

• 总酸含量为

$$\sum_{i=0}^{N-1} V_i \cdot B_i$$

并且只有满足以下条件的方案才是合法的：

1. 对所有 $i$，都有 $V_i \ge 0$；
2. 若 $A_i \notin [L_A, R_A]$，则必须有 $V_i = 0$；

$$\sum_{i=0}^{N-1} V_i \cdot A_i \le M_A$$

$$\sum_{i=0}^{N-1} V_i \cdot B_i \le M_B$$

你的任务是：对于每位朋友，求出在满足其所有约束的前提下，Peter 最多能调出多少升饮料。

---

实现细节

你需要实现 soft_drinks.h 中定义的以下函数：

void init(const std::vector<int>& A, const std::vector<int>& B);

init 函数只会在所有询问开始前被调用一次。

参数含义：

• A：长度为 $N$ 的数组，其中 A[i] 表示第 $i$ 种饮料每升含糖量；
• B：长度为 $N$ 的数组，其中 B[i] 表示第 $i$ 种饮料每升含酸量。

double friendDrink(int Ma, int Mb, int La, int Ra);

friendDrink 会对每位朋友调用一次。

参数含义：

• Ma：该朋友允许摄入的最大糖总量；
• Mb：该朋友允许摄入的最大酸总量；
• La, Ra：只能选用满足 $La \le A_i \le Ra$ 的饮料来调配。

该函数应返回一个 double，表示在不违反任何约束的情况下，Peter 最多能提供给这位朋友的饮料体积（升）。

---

误差要求

你的答案被认为正确，当且仅当其绝对误差或相对误差不超过 $10^{-6}$。

也就是说，若你的输出为 $a$，标准答案为 $b$，那么当

$$\frac{|a-b|}{\max(1, |b|)} \le 10^{-6}$$

时，你的答案会被接受。

---

本地测试

提供了本地评测器 Lgrader.cpp 以及对应头文件 soft_drinks.h。

本地评测输入格式如下：

• 第一行：两个整数 $N, Q$
• 接下来 $N$ 行：每行两个整数 $A_i, B_i$
• 接下来 $Q$ 行：每行四个整数 $M_A, M_B, L_A, R_A$

评测器会先调用 init，随后对每位朋友依次调用 friendDrink，并将返回值输出到标准输出。

---

数据范围

• $1 \le N, Q \le 10^5$
• $0 \le A_i, B_i, M_A, M_B, L_A, R_A \le 10^9$
• 对任意饮料，保证 $A_i \ne 0$ 或 $B_i \ne 0$

---

子任务

子任务	分值	N	Q	额外限制
0		-		样例
1	6	≤ 2	≤ 10^5	无
2	9	≤ 10^5		$M_A = M_B$
3	7			$M_A = 0,\ A_i = 0$
4	9	≤ 500		无
5	15	≤ 5000
6	7	≤ 10^5	≤ 1000	$(L_A, R_A) = (0, 10^9)$
7	18		≤ 10^5
8	29			无

只有通过某个子任务及其依赖子任务的全部测试，才能获得该子任务分数。

---

样例

样例输入（本地评测器格式）

4 3
4 0
2 8
6 4
3 6
8 2 4 6
8 2 3 6
0 10 0 10

样例调用

init({4, 2, 6, 3}, {0, 8, 4, 6})
friendDrink(8, 2, 4, 6): return 2
friendDrink(8, 2, 3, 6): return 2.0833333
friendDrink(0, 10, 0, 10): return 0