Problem Background

Problem Description

A team named "Powerhouse" is formed by $n$ OIers from all over the country, each with a strength value $a_i$. There are $m$ competitions inviting them to participate, with the $i$-th competition requiring a team of $k_i$ individuals. To decide whether they should participate in a certain competition, they have devised the following two measures of strength:

• Define the $x$-th order minimum strength as the number of ways to select $x$ individuals from these $n$ people such that the $\gcd$ of their strength values equals 1;

• Define the $x$-th order maximum strength as the sum of the $\gcd$ of all possible groups of $x$ individuals.

For each competition, please inform them of their $k_i$-th order minimum and maximum strength. Note that to keep the answer secret, you need to take the result modulo a secret modulus $p$.

Input Format

The first line contains three integers $n, m, p$, representing the number of team members, the number of competitions, and the secret modulus, respectively.

The second line contains $n$ integers, where the $i$-th integer represents the strength value $a_i$ of the $i$-th person.

The next $m$ lines each contain an integer $k_i$, representing the required number of participants for the $i$-th competition.

Output Format

Output $m$ lines, where the $i$-th line contains two integers $min_i, max_i$, representing the minimum and maximum strength for the $i$-th competition, respectively, modulo $p$.

Sample Input and Output

Input Sample #1

4 4 998244353
8 15 12 6
2
3
4
5

Output Sample #1

1 19
2 7
1 1
0 0

Input Sample #2

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

Output Sample #2

12 78
0 918
12 78
12 78

Input Sample #3

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

Output Sample #3

56 56
52 60
69 71

Notes

Sample 1 Explanation

For the first competition, which requires selecting 2 individuals, only the pair $(8, 15)$ has a $\gcd$ of 1, so the minimum strength is 1; the sum of $\gcd$ for all pairs is 19, so the maximum strength is 19.

For the second competition, which requires selecting 3 individuals, there are two pairs $(8, 15, 12)$ and $(8, 15, 6)$ with a $\gcd$ of 1, so the minimum strength is 2; the sum of $\gcd$ for all possible groups is 7, so the maximum strength is 7.

Data Range

For all data, $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}$.

This problem consists of 30 test cases, bundled testing, with subtasks and data point distribution as follows:

Hints

$\mathbb{P}$ denotes the set of all prime numbers, and $\gcd$ denotes the greatest common divisor.

见题面 Input 部分

见题面 Output 部分