Team Strength Assessment with Möbius Inversion

A team named "实力派" is composed of n OIers with individual strengths a_i. They have received m invitations to competitions; the i-th contest requires forming a team of k_i members. To decide whether to participate, they defined two measures for any integer x (in our queries, x=k_i):

• x-th minimum strength: the number of ways to pick x persons from the team such that the gcd of their strengths is 1. In formulas, if \(C(S, x)\) is the number of ways to choose a subset \(S\) of size \(x\) among those whose \(gcd\) equals 1, then \[ L(x)=\sum_{d\ge1}\mu(d)\cdot \binom{cnt(d)}{x}, \] where \(cnt(d)\) is the number of persons whose strength is divisible by \(d\), and \(\mu(\cdot)\) is the Möbius function.
• x-th maximum strength: the sum of the gcd of strengths over all subsets of x persons. That is, \[ H(x)=\sum_{d\ge1}\varphi(d)\cdot \binom{cnt(d)}{x}, \] where \(\varphi(\cdot)\) is the Euler totient function.

Your task is to answer for each contest the pair \(\bigl(L(k_i), H(k_i)\bigr)\), after taking the results modulo a secret modulus p.

Note: All formulas are given in \(\LaTeX\) format. Ensure your answers are computed modulo p.

inputFormat

The first line contains three integers n, m, p where n is the number of team members, m is the number of contests, and p is the modulus. The second line contains n integers \(a_1, a_2, \ldots, a_n\) representing the strength of each member. Each of the following m lines contains one integer k_i, which denotes the size of the team required for the i-th contest.

outputFormat

For each contest, output two integers separated by a space: the k_i-th minimum strength and the k_i-th maximum strength (i.e. \(L(k_i)\) and \(H(k_i)\)) modulo p.

sample

3 2 1000000007
1 2 3
1
2

1 6
3 3