题目背景

题目描述

来自全国各地的 $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$ 个测试点，采用捆绑测试，子任务及数据点分配如下：

提示

$\mathbb{P}$ 表示全体质数集合，$\gcd$ 表示最大公因数。