C. File Your Taxes
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Tax day is coming! Quinn is very worried about his taxes but does not want to go to a tax lawyer to file them. He's decided to navigate the world of taxes on his own to find the very best way to file his taxes. The country Quinn lives in has two tax systems in which you can report income to be taxed. You cannot report a total income higher than $$$m$$$ dollars.

A tax system is defined as follows:

  • A tax system consists of $$$n$$$ tax brackets.
  • The tax system is defined by two strictly increasing sequences $$$b$$$ and $$$t$$$ of sizes $$$n+1$$$ and $$$n$$$, respectively.
  • $$$b$$$ represents the tax bracket boundaries while $$$t$$$ represents the tax rates of the brackets. Specifically, the $$$i$$$-th tax bracket is defined by three numbers $$$b_i, b_{i+1}, t_i$$$, defining an interval $$$[b_i,b_{i+1}]$$$ that is taxed at a rate of $$$t_i\%$$$.
  • All of the tax brackets are disjoint and union to the full interval $$$[0,m]$$$. Therefore, $$$b_n=m$$$.
Evaluating how much tax you owe in a particular system depends on $$$s$$$, the starting point, and $$$u$$$, the income you report in that system. Then the income is represented by the interval $$$[s,s+u]$$$. For each bracket in the system, calculate the length of its intersection with the income interval and multiply it by the bracket's tax rate to get the tax paid in the bracket. Adding these taxes together yields the total tax paid in the system.

To actually report a total income of $$$x$$$, Quinn must first split it into $$$y$$$ and $$$z$$$ — the income he will report to tax system 1 and 2, respectively. Then the starting point for tax system 1 is $$$0$$$ and the starting point for tax system 2 is $$$y$$$. Help Quinn determine the minimum amount of taxes he must pay if he splits $$$x$$$ optimally. $$$y$$$ and $$$z$$$ must be non-negative, real values that sum to $$$x$$$.

However, Quinn does not yet know how much income he will earn this year, so he wants you to help him figure this out for multiple total incomes.

Input

The first line of input will consist of two integers $$$n$$$ and $$$m$$$ $$$(2 \le n \le 10^5, 1 \le m \le 10^9)$$$ — the number of tax brackets both tax systems have and the maximum total income that can be reported, respectively.

Following that are the descriptions of tax system 1 and 2, respectively. The input formats for both are identical and as follows:

The first line consists of a strictly increasing array $$$b$$$ of $$$n+1$$$ real numbers $$$(0.0 \le b_i \le m,b_0=0.0,b_n=m)$$$, representing the tax boundaries. Each value will have exactly two decimal places. The second line consists of a strictly increasing array $$$t$$$ of $$$n$$$ real numbers $$$(0.0 \le t_i \le 100.0)$$$, representing the tax rates. Each value will have exactly five decimal places.

The next line of input will consist of a single integer $$$q$$$ $$$(1 \le q \le 10^5)$$$ — the number of queries. The last $$$q$$$ lines of input will each consist of a single real number $$$(0.0 \le x_i \le m)$$$, representing a query for a total income. Each value will have exactly two decimal places.

Output

Output $$$q$$$ lines, each containing a single real number — the minimum tax paid for the respective query. Your answer will be accepted if it has an absolute or relative error of $$$10^{-6}$$$ with the judge's solution.

Example
Input
3 10
0.00 2.00 3.00 10.00
20.00000 30.00000 100.00000
0.00 1.00 4.00 10.00
0.00000 50.00000 60.00000
12
1.66
4.00
1.00
1.60
0.00
10.00
9.00
1.67
2.00
2.10
3.00
1.90
Output
0.33000000
1.20000000
0.00000000
0.30000000
0.00000000
4.80000000
4.20000000
0.33400000
0.40000000
0.43000000
0.70000000
0.38000000
Note

Tax System 1 is analogous to the ordinary income tax system in the US and Tax System 2 is analogous to the capital gains tax system in the US. This is, of course, a simplification of the US tax system. For example, you usually cannot choose how much of your income to distribute to each system. Do not use this material as financial, tax, or legal advice. For guidance on actual tax matters, consult a qualified tax professional or refer to official government resources. Also, do not forget to file your taxes.