Problem Description

In a 2D world there is a mountainous terrain. The mountain can be described by a function $f(x)$, meaning that at horizontal coordinate $x$ the altitude is $h=f(x)$. In this world there are $n+m$ sheep: $n$ goats and $m$ sheep. We know that the horizontal coordinate of the $i$-th goat is $p_i$, and the horizontal coordinate of the $j$-th sheep is $q_j$, but we do not know their altitudes. However, we know that the goats’ positions are concentrated in a higher altitude range, while the sheep’s positions are concentrated in a lower altitude range. You need to guess the mountain shape $f(x)$ from the distributions of goats and sheep, making both the variance of the goats’ altitudes and the variance of the sheep’s altitudes as small as possible, and at the same time making the goats’ altitudes as high as possible compared with the sheep’s 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_i)$$

be the average altitude of goats and sheep respectively. Your goal is to construct a function $f$ to minimize 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]}$$

Of course, you also need to ensure $\bar u > \bar v + 10^{-9}$.

For convenience, you must describe $f$ using a Fourier series. That is, 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 testdata guarantees that there exists an optimal solution satisfying the above limits.

This problem uses Special Judge. Given tolerance $\epsilon=10^{-E}$. Your answer is considered correct when the function $f$ you output and the function $f^*$ in the official answer satisfy $\operatorname{cost}(f)<\max(\epsilon+\operatorname{cost}(f^*),(1+\epsilon)\operatorname{cost}(f^*))$.

Constraints

For all testdata, it is guaranteed that $1 \le n,m \le 600$, $1 \le k \le \min\{\dfrac{n+m}{4},300\}$, $0 \le E \le 9$, $0\le |p_i|,|q_i| \le 10^9$.

It is guaranteed that in each testdata, under the condition that $p_i$ and $q_j$ are within the data range of this test point and the problem is solvable, they are generated uniformly at random.

Input Format

The input has 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$.

3 2 1 0
‐10838702 0 10838702
‐1 1

1 0

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

0.6648289523 ‐0.1433645347
0.6172866488 1.3647253547

见选手目录下的 mountain/mountain3.in 与 mountain/mountain3.ans。

见选手目录下的 mountain/mountain3.in 与 mountain/mountain3.ans。

Hint

Explanation for Sample 1

Observe that $\cos(10838702)=\cos(-10838702)\approx 1 =\cos(0)$, and $\cos(1)=\cos(-1)\approx 0.5403023$. So when $f(x)=\cos(x)$, almost all goats are at the same altitude, almost all sheep are at the same altitude, and the goats’ positions are higher than the sheep’s positions. In this case $\operatorname{cost}(f) \approx 0$, achieving the optimal solution.

Note that for any non-zero number $r$, the function $f(x)=r\cos(x)$ can also be considered an optimal solution.

Explanation for Sample 2

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)$, and its cost is approximately $3.908439063011$.

Subtasks

For all testdata, it is guaranteed that $1 \le n,m \le 600$, $1 \le k \le \min\{\dfrac{n+m}{4},300\}$, $0 \le E \le 9$, $0\le |p_i|,|q_i| \le 10^9$.

It is guaranteed that in each testdata, under the condition that $p_i$ and $q_j$ are within the data range of this test point and the problem is solvable, they are generated uniformly at random.

Translated by ChatGPT 5