{"raw_statement":[{"iden":"statement","content":"某二维世界中有一个山地，山体可以用一个函数 $f(x)$ 描述，其表示横坐标 $x$ 的位置海拔高度为 $h=f(x)$。这个世界里有 $n+m$ 只羊，其中有 $n$ 只山羊和 $m$ 只绵羊。我们知道第 $i$ 只山羊所在的横坐标是 $p_i$，第 $j$ 只绵羊所在的横坐标是 $q_j$，但不知道它们所在的高度。不过，我们知道山羊们所在的位置海拔集中在一个较高的范围，而绵羊们所在的位置海拔集中在一个较矮的范围。你需要根据山羊和绵羊的分布情况猜测山体形态 $f(x)$，使得山羊高度的方差和绵羊高度的方差都尽可能小，同时山羊高度尽可能高于绵羊高度。\n\n形式化地，令\n\n$$\n\\bar{u}=\\frac{1}{n}\\sum_{i=1}^n f(p_i)\n$$\n\n$$\n\\bar{v}=\\frac{1}{m}\\sum_{j=1}^m f(q_i)\n$$\n\n表示山羊、绵羊分别的平均高度，你的目标就是构造函数 $f$，最小化代价\n$$\n\\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]}\n$$\n当然，**你还需要保证 $\\bar u > \\bar v + 10^{-9}$**。\n\n方便起见，你需要使用傅里叶级数描述 $f$。即给定 $k$，你需要求出最优的形如 $f(x)=\\sum_{i=1}^k a_i\\cos(ix)+b_i\\sin(ix)$ 的函数 $f$，并输出 $a_i,b_i$ 表示答案。**请你保证 $10^{-9}\\le \\max_{i=1}^k\\{|a_i|,|b_i|\\} \\le 10^9$**。**数据保证存在满足上述限制的最优解。**\n\n本题开启 Special Judge。给定容错度 $\\epsilon=10^{-E}$。当你给出的函数 $f$ 与答案给出的函数 $f^*$ 满足 $\\operatorname{cost}(f)<\\max(\\epsilon+\\operatorname{cost}(f^*),(1+\\epsilon)\\operatorname{cost}(f^*))$ 时认为你的答案正确。"},{"iden":"input","content":"输入共三行。\n\n第一行三个整数 $n,m,k,E$；\n\n第二行 $n$ 个整数，第 $i$ 个数为 $p_i$；\n\n第三行 $m$ 个整数，第 $j$ 个数为 $q_j$。"},{"iden":"output","content":"输出 $k$ 行，每行两个浮点数 $a_i,b_i$。"},{"iden":"note","content":"### 样例 1 解释\n\n观察到 $\\cos(10838702)=\\cos(-10838702)\\approx 1 =\\cos(0)$，$\\cos(1)=\\cos(-1)\\approx 0.5403023$。即当 $f(x)=\\cos(x)$ 时，所有山羊几乎均位于同一海拔、所有绵羊均位于同一海拔、山羊所在位置均高于绵羊所在位置。此时 $\\operatorname{cost}(f) \\approx 0$ 取得最优解。\n\n值得注意的是，对于任何非零数 $r$，函数 $f(x)=r\\cos(x)$ 均可视为最优解。\n\n### 样例 2 解释\n\n最优函数（之一）约为 $f(x)=0.6648289523\\cos(x)-0.1433645347\\sin(x)+0.6172866488\\cos(2x)+1.3647253547\\sin(2x)$，其代价约为 $3.908439063011$。\n\n### 子任务\n\n对于所有测试数据，保证 $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$。\n\n**保证每个测试数据中，$p_i$ 和 $q_j$ 均在该测试点数据范围内以及问题有解的条件下均匀随机生成。**\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/91am18bk.png)"}],"translated_statement":null,"sample_group":[["3 2 1 0\n‐10838702 0 10838702\n‐1 1","1 0"],["4 4 2 0\n1 3 5 7\n2 4 6 8","0.6648289523 ‐0.1433645347\n0.6172866488 1.3647253547"],["见选手目录下的 mountain/mountain3.in 与 mountain/mountain3.ans。","见选手目录下的 mountain/mountain3.in 与 mountain/mountain3.ans。"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}