{"raw_statement":[{"iden":"background","content":"翻译自 [ROIR 2022 D2T2](https://neerc.ifmo.ru/school/archive/2021-2022/ru-olymp-regional-2022-day2.pdf)。"},{"iden":"statement","content":"有两个由 $n$ 个不同整数组成的序列 $A = [a_1, a_2, \\dots , a_n]$ 和 $B = [b_1, b_2, \\dots , b_n]$。将它们组合成 $n^2$ 个分数，形式为 $\\frac{a_i}{b_j}$，并将每个分数约分后按递增顺序排序。\n\n给定一个数字 $q$ 和 $q$ 个整数 $c_1, c_2, \\dots , c_q$。对于每个 $c_i$，请输出上面所说的 $n^2$ 个分数中第 $c_i$ 小的分数。"},{"iden":"input","content":"第一行包含两个整数 $n$ 和 $q$。\n\n第二行包含 $n$ 个不同的整数 $a_1, a_2, \\dots, a_n$。\n\n第三行包含 $n$ 个不同的整数 $b_1, b_2, \\dots, b_n$。\n\n第四行包含 $q$ 个不同的整数 $c_1, c_2, \\dots, c_q$。"},{"iden":"output","content":"输出 $q$ 行。第 $i$ 行输出按递增顺序得到的第 $c_i$ 个分数。分数 $\\frac{p}{q}$ 应以 `p q` 的格式输出，并且应为最简分数。"},{"iden":"note","content":"在样例中，初始的分数列表如下：\n\n$$\n\\left[\n\\frac{3}{2},\n\\frac{3}{3},\n\\frac{3}{4},\n\\frac{3}{5},\n\\frac{4}{2},\n\\frac{4}{3},\n\\frac{4}{4},\n\\frac{4}{5},\n\\frac{1}{2},\n\\frac{1}{3},\n\\frac{1}{4},\n\\frac{1}{5},\n\\frac{2}{2},\n\\frac{2}{3},\n\\frac{2}{4},\n\\frac{2}{5}\n\\right],\n$$\n\n经过约分后，得到：\n\n$$\n\\left[\n\\frac{3}{2},\n\\frac{1}{1},\n\\frac{3}{4},\n\\frac{3}{5},\n\\frac{2}{1},\n\\frac{4}{3},\n\\frac{1}{1},\n\\frac{4}{5},\n\\frac{1}{2},\n\\frac{1}{3},\n\\frac{1}{4},\n\\frac{1}{5},\n\\frac{1}{1},\n\\frac{2}{3},\n\\frac{1}{2},\n\\frac{2}{5}\n\\right],\n$$\n\n最后按递增顺序排序，得到：\n\n$$\n\\left[\n\\frac{1}{5},\n\\frac{1}{4},\n\\frac{1}{3},\n\\frac{2}{5},\n\\frac{1}{2},\n\\frac{1}{2},\n\\frac{3}{5},\n\\frac{2}{3},\n\\frac{3}{4},\n\\frac{4}{5},\n\\frac{1}{1},\n\\frac{1}{1},\n\\frac{1}{1},\n\\frac{4}{3},\n\\frac{3}{2},\n\\frac{2}{1}\n\\right].\n$$\n\n本题使用捆绑测试。\n\n| 子任务 | 分值 | 特殊性质 |\n| :----------: | :----------: | :----------: |\n| $1$ | $14$ | $n\\le50$ |\n| $2$ | $13$ | $n\\le500$ |\n| $3$ | $15$ | $q,c_i\\le100$ |\n| $4$ | $21$ | $c_i\\le10^5$ |\n| $5$ | $37$ |  |\n\n对于 $100\\%$ 的数据，$1 \\leq n \\leq 10^5$，$1 \\leq q \\leq 10^5$ 且 $q \\leq n^2,n\\times q\\le10^5$（所以实际上 $q\\le1000\\sqrt[3]{10}\\approx2154$），$1 \\leq a_i,b_i \\leq 10^6$，$1 \\leq c_i \\leq n^2$。"}],"translated_statement":null,"sample_group":[["4 8\n3 4 1 2\n2 3 4 5\n1 16 2 4 5 6 10 15","1 5\n2 1\n1 4\n2 5\n1 2\n1 2\n4 5\n3 2"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}