{"raw_statement":[{"iden":"background","content":"![](https://cdn.luogu.com.cn/upload/image_hosting/z8ednvb2.png)"},{"iden":"statement","content":"来自全国各地的 $n$ 位 OIer 组成了一个名为“实力派”的团队，每个人有一个实力值 $a_i$。共有 $m$ 场比赛向他们发送了参赛邀请，其中第 $i$ 场比赛要求 $k_i$ 个人组成一个队伍参加。为了决定他们是否应该参加某场比赛，他们想出了如下两个衡量实力的数据：\n\n- 定义 $x$ 阶最低实力表示从这 $n$ 个人中选出 $x$ 个人，使得这 $x$ 个人实力值的 $\\gcd=1$ 的方案数；\n\n- 定义 $x$ 阶最高实力表示从这 $n$ 个人中选出 $x$ 个人，所有方案的 $x$ 个人的 $\\gcd$ 之和。\n\n请你对于每场比赛，告诉他们他们在这场比赛中的 $k_i$ 阶最低实力和最高实力。对了，为了不让别人听懂，你需要将答案对一个秘密模数 $p$ 取模。"},{"iden":"input","content":"第一行三个整数 $n,m,p$，分别表示团队人数，比赛场数及秘密模数；\n\n第二行 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个人的实力值 $a_i$。\n\n接下来 $m$ 行，第 $i$ 行一个整数 $k_i$，表示第 $i$ 场比赛的要求参赛人数。"},{"iden":"output","content":"输出共 $m$ 行，第 $i$ 行两个整数 $min_i,max_i$，分别表示他们在第 $i$ 场比赛中的最低实力和最高实力，答案对 $p$ 取模。"},{"iden":"note","content":"**样例** $\\mathbf{1}$ **解释**\n\n第一场比赛要求选出 $2$ 人参加，仅有 $(8,15)$ 一种方案的 $\\gcd=1$，因此最低实力为 $1$；所有方案的 $\\gcd$ 之和为 $19$，因此最高实力为 $19$；\n\n第二场比赛要求选出 $3$ 人参加，有 $(8,15,12)$ 和 $(8,15,6)$ 两种 $\\gcd=1$ 的方案，因此最低实力为 $2$；所有方案的 $\\gcd$ 之和为 $7$，因此最高实力为 $7$。\n\n**数据范围**\n\n对于所有数据，$1\\leq n,m,k_i\\leq 2\\times 10^5$，$1\\leq a_i\\leq 10^6$，$10^7\\leq p\\leq 10^9$，$p\\in \\mathbb{P}$。\n\n本题共 $30$ 个测试点，**采用捆绑测试**，子任务及数据点分配如下：\n\n| 子任务编号 | 数据点编号 | 特殊性质 | 分值 | 时限 |\n| :-: | :-: | :-: | :-: | :-: |\n| $0$ | $1\\sim 4$ | $n\\leq 20$ | $10$ | $1s$ |\n| $1$ | $5\\sim 8$ | $n,a_i\\leq 300$ | $10$ | $1s$ | \n| $2$ | $9\\sim 12$ | $k_i\\leq 2$ | $20$ | $1.5s$ |\n| $3$ | $13\\sim 16$ | $a_i\\leq 3$ | $10$ | $1s$ |\n| $4$ | $17\\sim 22$ | $a_i\\leq 10^5$ | $20$ | $1s$ |\n| $5$ | $23\\sim 30$ | 无特殊性质 | $30$ | $1.5s$ |\n\n**提示**\n\n$\\mathbb{P}$ 表示全体质数集合，$\\gcd$ 表示最大公因数。"}],"translated_statement":null,"sample_group":[["4 4 998244353\n8 15 12 6\n2\n3\n4\n5","1 19\n2 7\n1 1\n0 0"],["6 4 19260817\n11 45 14 19 19 810\n2\n1\n2\n2","12 78\n0 918\n12 78\n12 78"],["8 3 19491001\n3 2 2 3 1 2 1 2\n5\n3\n4","56 56\n52 60\n69 71"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}