Problem Description

In a two-dimensional world, there is a mountainous terrain described by a function \( f(x) \), which represents the altitude \( h = f(x) \) at the horizontal coordinate \( x \). There are \( n + m \) sheep in this world, consisting of \( n \) goats and \( m \) sheep. We know the horizontal coordinates \( p_i \) of the \( i \)-th goat and \( q_j \) of the \( j \)-th sheep, but not their altitudes. However, we know that the altitudes of the goats are concentrated in a higher range, while the altitudes of the sheep are concentrated in a lower range. You need to guess the shape of the mountain \( f(x) \) based on the distribution of goats and sheep, such that the variance of the goat altitudes and the variance of the sheep altitudes are both minimized, while the goat altitudes are as high as possible compared to the sheep altitudes.

Formally, let

\[ \bar{u} = \frac{1}{n} \sum_{i=1}^n f(p_i) \]

\[ \bar{v} = \frac{1}{m} \sum_{j=1}^m f(q_j) \]

represent the average altitudes of goats and sheep respectively. Your goal is to construct the function \( f \) that minimizes the cost

\[ \operatorname{cost}(f) = \frac{1}{\bar{u} - \bar{v}} \sqrt{\left[ \sum_{i=1}^n (f(p_i) - \bar{u})^2 \right] + \left[ \sum_{j=1}^m (f(q_j) - \bar{v})^2 \right]} \]

Additionally, you need to ensure \( \bar{u} > \bar{v} + 10^{-9} \).

For convenience, you need to describe \( f \) using a Fourier series. Given \( k \), you need to find the optimal function of the form \( f(x) = \sum_{i=1}^k a_i \cos(ix) + b_i \sin(ix) \) and output \( a_i, b_i \) as the answer. Please ensure \( 10^{-9} \le \max_{i=1}^k \{ |a_i|, |b_i| \} \le 10^9 \). The data guarantees the existence of an optimal solution that satisfies the above constraints.

This problem includes a Special Judge. Given a tolerance \( \epsilon = 10^{-E} \). Your function \( f \) is considered correct if it satisfies \( \operatorname{cost}(f) < \max(\epsilon + \operatorname{cost}(f^*), (1 + \epsilon) \operatorname{cost}(f^*)) \) compared to the answer function \( f^* \).

Input Format

The input consists of three lines.

The first line contains four integers \( n, m, k, E \);

The second line contains \( n \) integers, where the \( i \)-th number is \( p_i \);

The third line contains \( m \) integers, where the \( j \)-th number is \( q_j \).

Output Format

Output \( k \) lines, each containing two floating-point numbers \( a_i, b_i \).

Sample Input and Output

Sample Input #1

3 2 1 0
-10838702 0 10838702
-1 1

Sample Output #1

1 0

Sample Input #2

4 4 2 0
1 3 5 7
2 4 6 8

Sample Output #2

0.6648289523 -0.1433645347
0.6172866488 1.3647253547

Sample Input #3

See the file in the contestant directory under mountain/mountain3.in and mountain/mountain3.ans.

Sample Output #3

See the file in the contestant directory under mountain/mountain3.in and mountain/mountain3.ans.

Notes

Sample 1 Explanation

Notice that \( \cos(10838702) = \cos(-10838702) \approx 1 = \cos(0) \) and \( \cos(1) = \cos(-1) \approx 0.5403023 \). When \( f(x) = \cos(x) \), all goats are almost at the same altitude, all sheep are at the same altitude, and the goats are higher than the sheep. Thus, \( \operatorname{cost}(f) \approx 0 \) achieves the optimal solution.

It is worth noting that for any non-zero number \( r \), the function \( f(x) = r \cos(x) \) can be considered an optimal solution.

Sample 2 Explanation

One of the optimal functions is approximately \( f(x) = 0.6648289523 \cos(x) - 0.1433645347 \sin(x) + 0.6172866488 \cos(2x) + 1.3647253547 \sin(2x) \), with a cost of approximately \( 3.908439063011 \).

Subtasks

For all test data, it is guaranteed that \( 1 \le n, m \le 600 \), \( 1 \le k \le \min\{\frac{n+m}{4}, 300\} \), \( 0 \le E \le 9 \), \( 0 \le |p_i|, |q_i| \le 10^9 \).

It is guaranteed that within each test data, \( p_i \) and \( q_j \) are uniformly randomly generated within the data range of the test point and under the condition that the problem has a solution.

见题面 Input 部分

见题面 Output 部分