soft_drinks

Peter has recently taken up mixing soft drinks as a part-time hobby. He has purchased the access to an infinite supply of $N$ different drink types. Each $i$-th drink type $(0 \leq i < N)$ contains $A_i$ grams of sugar per liter and $B_i$ grams of acids per liter.

Peter is hosting a gathering at his home and has invited $Q$ of his closest friends. Each friend is quite health-conscious and picky and arrives with the following constraints:

• $M_A$: the maximum total weight (in grams) of sugar they are willing to consume.
• $M_B$: the maximum total weight (in grams) of acids they are willing to consume.
• $L_A,R_A$: they will only drink from those drink types whose sugar concentration (sugar grams per liter) is in the range $[L_A,R_A]$ (inclusive).

Peter can mix varying quantities (including fractional amounts) of each drink type to prepare a custom mocktail. Formally, let the real non-negative $V_i$ be the amount (in liters) of the $i$-th drink used in the final mixture. Then:

• The total volume of the mocktail is $\sum_{i=0} ^{N-1} V_i$ liters.
• The total weight of sugar in the mixture is $\sum_{i=0} ^{N-1} V_i \cdot A_i$ grams.
• The total weight of acids in the mixture is $\sum_{i=0} ^{N-1} V_i \cdot B_i$ grams.

Your task is to help Peter determine the maximum total volume (in liters) he can serve to each friend, while respecting their individual constraints.

Implementation details

You need to implement the following functions as defined in soft_drinks.h:

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

The init function gets called exactly once before any other queries. Its parameters correspond to:

• A: a vector of length $N$ where A[i] is the sugar content per liter of the $i$-th drink.
• B: a vector of length $N$ where B[i] is the acid content per liter of the $i$-th drink.

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

The friendDrink function gets called once for each of the $Q$ friends. Its parameters correspond to:

• Ma: the maximum total weight of sugar the friend will consume.
• Mb: the maximum total weight of acids the friend will consume.
• La, Ra: the inclusive bounds on the sugar concentration of the drink types the friend will accept drinking from.

The function should return a double representing the maximum volume (in liters) that Peter can serve this friend without violating any of his constraints.

Your answer is considered correct, if its absolute or relative error doesn't exceed $10^{-6}$. Namely, if your answer is $a$, and the correct answer is $b$, then your answer is accepted, if $$\frac{|a-b|}{max(1,|b|)} \leq 10^{-6}$

Local testing

A local grader Lgrader.cpp and the corresponding header file soft_drinks.h are provided.

Input format:

• First line: integers $N$ and $Q$.
• Next $N$ lines: two integers $A_i$ and $B_i$ for each drink.
• Next $Q$ lines: four integers $M_A, M_B, L_A$, and $R_A$ for each friend.

The grader will call init, followed by friendDrink for each friend, printing the result to standard output.

Restrictions

• $1 \leq N,Q \leq 10^5$
• $0 \leq A_i, B_i, M_A, M_B, L_A, R_A \leq 10^9$
• Either $A_i \not= 0$ or $B_i \not= 0$

Example

stdin

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

Interaction

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