实力派


来自全国各地的 $n$ 位 OIer 组成了一个名为“实力派”的团队，每个人有一个实力值 $a_i$。共有 $m$ 场比赛向他们发送了参赛邀请，其中第 $i$ 场比赛要求 $k_i$ 个人组成一个队伍参加。为了决定他们是否应该参加某场比赛，他们想出了如下两个衡量实力的数据： - 定义 $x$ 阶最低实力表示从这 $n$ 个人中选出 $x$ 个人，使得这 $x$ 个人实力值的 $\gcd=1$ 的方案数； - 定义 $x$ 阶最高实力表示从这 $n$ 个人中选出 $x$ 个人，所有方案的 $x$ 个人的 $\gcd$ 之和。 请你对于每场比赛，告诉他们他们在这场比赛中的 $k_i$ 阶最低实力和最高实力。对了，为了不让别人听懂，你需要将答案对一个秘密模数 $p$ 取模。

第一行三个整数 $n,m,p$，分别表示团队人数，比赛场数及秘密模数； 第二行 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个人的实力值 $a_i$。 接下来 $m$ 行，第 $i$ 行一个整数 $k_i$，表示第 $i$ 场比赛的要求参赛人数。

输出共 $m$ 行，第 $i$ 行两个整数 $min_i,max_i$，分别表示他们在第 $i$ 场比赛中的最低实力和最高实力，答案对 $p$ 取模。

4 4 998244353
8 15 12 6
2
3
4
5

1 19
2 7
1 1
0 0

6 4 19260817
11 45 14 19 19 810
2
1
2
2

12 78
0 918
12 78
12 78

8 3 19491001
3 2 2 3 1 2 1 2
5
3
4

56 56
52 60
69 71

**样例** $\mathbf{1}$ **解释** 第一场比赛要求选出 $2$ 人参加，仅有 $(8,15)$ 一种方案的 $\gcd=1$，因此最低实力为 $1$；所有方案的 $\gcd$ 之和为 $19$，因此最高实力为 $19$； 第二场比赛要求选出 $3$ 人参加，有 $(8,15,12)$ 和 $(8,15,6)$ 两种 $\gcd=1$ 的方案，因此最低实力为 $2$；所有方案的 $\gcd$ 之和为 $7$，因此最高实力为 $7$。 **数据范围** 对于所有数据，$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}$。 本题共 $30$ 个测试点，**采用捆绑测试**，子任务及数据点分配如下： | 子任务编号 | 数据点编号 | 特殊性质 | 分值 | 时限 | | :-: | :-: | :-: | :-: | :-: | | $0$ | $1\sim 4$ | $n\leq 20$ | $10$ | $1s$ | | $1$ | $5\sim 8$ | $n,a_i\leq 300$ | $10$ | $1s$ | | $2$ | $9\sim 12$ | $k_i\leq 2$ | $20$ | $1.5s$ | | $3$ | $13\sim 16$ | $a_i\leq 3$ | $10$ | $1s$ | | $4$ | $17\sim 22$ | $a_i\leq 10^5$ | $20$ | $1s$ | | $5$ | $23\sim 30$ | 无特殊性质 | $30$ | $1.5s$ | **提示** $\mathbb{P}$ 表示全体质数集合，$\gcd$ 表示最大公因数。