Background

Problem Description

There are $n$ OIers from all over the country who form a team called "实力派" (shílìpài). Each person has a strength value $a_i$. There are $m$ contests that send them invitations. In the $i$-th contest, they are required to form a team of $k_i$ people to participate. To decide whether they should join a contest, they came up with the following two measures of strength:

• Define the $x$-th order minimum strength as the number of ways to choose $x$ people from these $n$ people such that the $\gcd=1$ of the chosen $x$ people's strength values;

• Define the $x$-th order maximum strength as the sum of the $\gcd$ of the chosen $x$ people over all possible choices.

For each contest, please tell them the $k_i$-th order minimum strength and maximum strength for that contest. Also, to keep others from understanding, you need to take the answers 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 contests, and the secret modulus, respectively.

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

The next $m$ lines each contain one integer $k_i$, meaning the required number of participants for the $i$-th contest.

Output Format

Output $m$ lines. The $i$-th line contains two integers $min_i,max_i$, representing the minimum strength and maximum strength in the $i$-th contest, with answers taken modulo $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

Hint

Sample $\mathbf{1}$ Explanation

In the first contest, they need to choose $2$ people. Only the choice $(8,15)$ has $\gcd=1$, so the minimum strength is $1$. The sum of $\gcd$ over all choices is $19$, so the maximum strength is $19$.

In the second contest, they need to choose $3$ people. There are two choices with $\gcd=1$: $(8,15,12)$ and $(8,15,6)$. Therefore, the minimum strength is $2$. The sum of $\gcd$ over all choices is $7$, so the maximum strength is $7$.

Constraints

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$, and $p\in \mathbb{P}$.

This problem has a total of $30$ test points and uses bundled tests. The subtasks and test point distribution are as follows:

Hint

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

Translated by ChatGPT 5