Mountain Fourier Optimization

In a two-dimensional world there is a mountain whose profile is described by a function \(f(x)\), representing the altitude \(h=f(x)\) at horizontal position \(x\). There are a total of \(n+m\) sheep in this world: \(n\) mountain goats and \(m\) ordinary sheep. The \(i\)th mountain goat is located at \(p_i\) and the \(j\)th sheep is at \(q_j\); however, their altitudes are unknown. It is known that the altitudes at mountain goats’ positions are concentrated in a higher range, while those at the sheep’s positions are in a lower range.

Your task is to guess the shape of the mountain, \(f(x)\), based on these distributions. In particular, you want the altitudes of the mountain goats to have as small a variance as possible and similarly for the sheep, while ensuring that the mountain goats are as high above the sheep as possible.

Formally, let \[ \bar{u}=\frac{1}{n}\sum_{i=1}^n f(p_i), \quad \bar{v}=\frac{1}{m}\sum_{j=1}^m f(q_j), \] then your goal is to construct \(f\) (in a prescribed Fourier series form) so that the cost \[ \operatorname{cost}(f)=\frac{1}{\bar{u}-\bar{v}} \sqrt{\sum_{i=1}^n (f(p_i)-\bar{u})^2+\sum_{j=1}^m (f(q_j)-\bar{v})^2} \] is minimized. Of course, you must also guarantee that \[ \bar{u} > \bar{v} + 10^{-9}. \]

To simplify matters, you are required to describe \(f\) by a Fourier series. Given an integer \(k\), determine the optimal function of the form \[ f(x)=\sum_{i=1}^k a_i\cos(ix)+b_i\sin(ix), \] and output the coefficients \(a_i, b_i\) for \(i=1,2,\ldots,k\). Please also ensure that \[ 10^{-9} \le \max_{1\le i\le k}\{ |a_i|,|b_i|\} \le 10^9. \]

Special Judge: The judge uses a tolerance of \(\epsilon=10^{-E}\). Your answer \(f\) is accepted if \[ \operatorname{cost}(f) < \max(\epsilon+\operatorname{cost}(f^*),(1+\epsilon)\operatorname{cost}(f^*)) \] where \(f^*\) is the optimal function.

Input Format and Output Format are described below.

inputFormat

The first line of input contains four numbers: an integer \(n\) (number of mountain goats), an integer \(m\) (number of sheep), an integer \(k\) (number of Fourier terms), and an integer \(E\) (defining the tolerance \(\epsilon=10^{-E}\)).

The second line contains \(n\) space-separated real numbers: \(p_1, p_2, \ldots, p_n\), the positions of the mountain goats.

The third line contains \(m\) space-separated real numbers: \(q_1, q_2, \ldots, q_m\), the positions of the sheep.

outputFormat

Output \(2k\) real numbers separated by spaces representing the coefficients \(a_1, b_1, a_2, b_2, \ldots, a_k, b_k\) of the Fourier series representation of \(f(x)\). The coefficients must satisfy the constraint \(10^{-9} \le \max_{1\le i\le k}\{|a_i|,|b_i|\} \le 10^9\), and the function \(f(x)\) must satisfy \(\bar{u} > \bar{v} + 10^{-9}\) and achieve a near-optimal cost as defined above.

sample

3 3 2 9
0 1 2
3 4 5

1 0 0 0