Problem Description

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 $\textbf{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 \times A_i$ grams.
• The total weight of acids in the mixture is $\sum_{i=0}^{N-1} V_i \times B_i$ grams.

Your task is to help Peter determine the $\textbf{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 $\texttt{soft\_drinks.h}$:

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

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

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

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

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

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

The function should return a $\texttt{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|)} \le 10^{-6}$.

Local Testing

A local grader $\texttt{Lgrader.cpp}$ and the corresponding header file $\texttt{soft\_drinks.h}$ are provided.

Input Format

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 $\texttt{init}$, followed by $\texttt{friendDrink}$ for each friend, printing the result to standard output.

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

2
2.0833333
0

Hint

Constraints

• $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 \neq 0$ or $B_i \neq 0$.

Subtasks

You get the points for a given subtask only if you correctly pass all tests in it and all other subtasks that are included in it.