You are given a polynomial \(p(x) = a_0 + a_1 x + a_2 x^2 + ... + a_m x^m\) of degree \(m\). In addition, you will have \(n\) real numbers \(x_1,...,x_n\). You need to calculate \(p(x_i)\) for each \(i \in \{1,..n\}\).

However, evaluating a polynomial gets more complex as its degree increases. Therefore you must use an approximation whenever it is possible.

To approximate \(p(x)\), you will compute \(T(x) = p(x_0) + p'(x_0) \cdot (x-x_0) + \frac{p''(x_0)}{2} \cdot (x-x_0)^2\), where \(|x - x_0| < \epsilon = 10^{-3}\). \(x_0\) can be any of the previous queries, for which you already directly computed the polynomial.

Input

The first line contains two integers, \(m\) and \(n\).

The next line contains \(m+1\) real numbers, which are polynomial coefficients. The first one is \(a_0\) and the last one is \(a_m\).

The last line contains \(n\) real numbers which correspond to query points where \(p(x)\) will be evaluated.

• \(0 \le m \le 5 \cdot 10^4\)
• \(1 \le n \le 5 \cdot 10^4\)
• \(a_m \neq 0\)
• \(|a_i| \leq 100\)
• \(|x_i| < 0.5\)
• \(a_i\) and \(x_i\) will not be more precise than \(10^{-4}\)

Output

Print the answer of each query with spaces in-between on the same single line and in the given order. Your answer will be considered correct if its absolute or relative error does not exceed \(10^{-6}\). Formally, let your answer be \(a\) and the jury's answer \(b\). Your answer will be considered correct if \(\frac{|a - b|}{max(1, |b|)} \le 10^{-6}\).

Example

Input 1:

2 3
1 0.5 3
0 0.1 0.0001

Output 1:

1 1.08 1.00005

Input 2:

2 3
1 1 1
0.1 0.1001 0.0999

Output 2:

1.11 1.11012 1.10988

Input 3:

2 3
1 1 1
0.1 0.1005 0.101

Output 3:

1.11 1.1106 1.111201

Explanation

Input 1: \(p(x) = 1 + 0.5x + 3x^2\)

First two queries \(p(0)\) and \(p(0.1)\) are computed directly. We can approximate \(p(0.0001) \approx T(0.0001) = p(0) + p'(0) \cdot (0.0001-0) + \frac{p''(0)}{2} \cdot (0.0001-0)^2\).

Input 2: The first query is directly calculated. The second and third ones are approximated.

Input 3: The first query is directly calculated. The second one is approximated. The third one is directly calculated.