Determining the Feasible Range for x₁ in a Quadratic Chain Equation

You are given a quadratic equation in n real variables \(x_i\) (for \(i=1,2,\dots,n\)) of the following form:

$$\sum_{i=1}^{n}a_i x_i^2+\sum_{i=1}^{n-1}b_i x_i x_{i+1}=m.$$

Here, the coefficients \(a_i\) and \(b_i\) (for \(i=1,2,\dots,n\) and \(i=1,2,\dots,n-1\) respectively) and the constant \(m\) are given real numbers. Your task is to determine the range of possible values for \(x_1\) such that there exist real numbers \(x_2,x_3,\dots,x_n\) satisfying the equation. It is guaranteed that the feasible set for \(x_1\) is bounded (i.e. both a lower bound and an upper bound exist).

Hint: One way to approach this problem is to fix \(x_1\) and eliminate the remaining variables by recursively completing the square. In particular, define a sequence \(A_n, A_{n-1}, \dots, A_1\) by:

[ \begin{aligned} A_n &= a_n,\ A_i &= a_i - \frac{b_i^2}{4A_{i+1]}}, \quad 1\le i\le n-1. \end{aligned} ]

Then, the minimum (or optimal) value achievable for the quadratic form given a fixed \(x_1\) can be shown to be \(A_1 x_1^2\). In order for the equation to have a solution, we must have:

[ A_1 x_1^2 = m \quad \Longleftrightarrow \quad x_1^2 = \frac{m}{A_1}. ]

Thus, the range for \(x_1\) is given by

[ -\sqrt{\frac{m}{A_1}} \le x_1 \le \sqrt{\frac{m}{A_1}}. ]

</p>

Output the lower and upper bounds of \(x_1\) (with an absolute or relative error of at most 1e-6).

inputFormat

The input consists of four lines:

1. An integer n (\(n \ge 2\)).
2. n space-separated real numbers representing \(a_1, a_2, \dots, a_n\).
3. n-1 space-separated real numbers representing \(b_1, b_2, \dots, b_{n-1}\).
4. A real number m.

outputFormat

Output two space-separated real numbers: the lower bound and the upper bound for \(x_1\), computed as:

[ -\sqrt{\frac{m}{A_1}} \quad \text{and} \quad \sqrt{\frac{m}{A_1}}, ]

where \(A_1\) is computed recursively as shown in the problem description. The answers must be accurate within an absolute or relative error of 1e-6.

sample

2
4 4
4
1

-0.5773502691896257 0.5773502691896257