CF1848E.Vika and Stone Skipping

In Vika's hometown, Vladivostok, there is a beautiful sea.

Often you can see kids skimming stones. This is the process of throwing a stone into the sea at a small angle, causing it to fly far and bounce several times off the water surface.

Vika has skimmed stones many times and knows that if you throw a stone from the shore perpendicular to the coastline with a force of $f$, it will first touch the water at a distance of $f$ from the shore, then bounce off and touch the water again at a distance of $f - 1$ from the previous point of contact. The stone will continue to fly in a straight line, reducing the distances between the points where it touches the water, until it falls into the sea.

Formally, the points at which the stone touches the water surface will have the following coordinates: $f$, $f + (f - 1)$, $f + (f - 1) + (f - 2)$, ... , $f + (f - 1) + (f - 2) + \ldots + 1$ (assuming that $0$ is the coordinate of the shoreline).

Once, while walking along the embankment of Vladivostok in the evening, Vika saw a group of guys skipping stones across the sea, launching them from the same point with different forces.

She became interested in what is the maximum number of guys who can launch a stone with their force $f_i$, so that all $f_i$ are different positive integers, and all $n$ stones touched the water at the point with the coordinate $x$ (assuming that $0$ is the coordinate of the shoreline).

After thinking a little, Vika answered her question. After that, she began to analyze how the answer to her question would change if she multiplied the coordinate $x$ by some positive integers $x_1$, $x_2$, ... , $x_q$, which she picked for analysis.

Vika finds it difficult to cope with such analysis on her own, so she turned to you for help.

Formally, Vika is interested in the answer to her question for the coordinates $X_1 = x \cdot x_1$, $X_2 = X_1 \cdot x_2$, ... , $X_q = X_{q-1} \cdot x_q$. Since the answer for such coordinates can be quite large, find it modulo $M$. It is guaranteed that $M$ is prime.

在维卡的家乡符拉迪沃斯托克，有一片美丽的海洋。

人们常常能看到孩子们打水漂。这一过程是将石子以较小的角度抛向海面，使其飞行较远距离，并在水面上多次弹跳。

维卡曾多次打水漂，她知道：若从海岸线垂直向海中以力度 $f$ 抛出石子，则石子首次接触水面的位置距海岸线为 $f$；随后弹起，并在距前一次接触点 $f - 1$ 的位置再次触水。石子将继续沿直线飞行，且每次触水点之间的距离逐次减小 $1$，直至最终沉入海中。

形式化地，石子接触水面各点的坐标依次为：
$f$，$f + (f - 1)$，$f + (f - 1) + (f - 2)$，…，$f + (f - 1) + (f - 2) + \ldots + 1$
（假设海岸线位置的坐标为 $0$）。

某天傍晚，维卡沿着符拉迪沃斯托克的海堤散步时，看到一群小伙子正朝海面打水漂——他们均从同一点出发，但各自施加的力度不同。

维卡由此产生了一个问题：最多有多少名小伙子能以各自的力度 $f_i$ 打水漂，使得所有 $f_i$ 均为互不相同的正整数，且所有 $n$ 颗石子最终都在坐标为 $x$ 的同一点处接触水面（仍设海岸线坐标为 $0$）？

稍作思考后，维卡便得出了该问题的答案。接着，她开始进一步分析：若将坐标 $x$ 分别乘以若干给定的正整数 $x_1, x_2, \dots, x_q$（这些数由她选定用于分析），答案将如何变化？

维卡独自完成此类分析颇为困难，因此她向你求助。

形式化地说，维卡希望得到对应于以下坐标的原问题答案：
$X_1 = x \cdot x_1$，$X_2 = X_1 \cdot x_2$，…，$X_q = X_{q-1} \cdot x_q$。
由于这些坐标对应的答案可能非常大，请对质数 $M$ 取模输出结果。题目保证 $M$ 是质数。

The first line of the input contains three integers $x$ ($1 \le x \le 10^9$), $q$ ($1 \le q \le 10^5$) and $M$ ($100 \le M \le 2 \cdot 10^9$) — the initial coordinate for which Vika answered the question on her own, the number of integers $x_i$ by which Vika will multiply the initial coordinate and prime module $M$.

The second line of the input contains $q$ integers $x_1, x_2, x_3, \ldots, x_q$ ($1 \le x_i \le 10^6$) — the integers described in the statement.

输入的第一行包含三个整数 $x$（$1 \le x \le 10^9$）、$q$（$1 \le q \le 10^5$）和 $M$（$100 \le M \le 2 \cdot 10^9$）——分别表示维卡自行回答问题时的初始坐标、维卡将用于乘以初始坐标的整数 $x_i$ 的个数，以及质数模数 $M$。

输入的第二行包含 $q$ 个整数 $x_1, x_2, x_3, \ldots, x_q$（$1 \le x_i \le 10^6$）——即题目描述中提到的那些整数。

Output $q$ integers, where the $i$-th number corresponds to the answer to Vika's question for the coordinate $X_i$. Output all the answers modulo $M$.

输出 $q$ 个整数，其中第 $i$ 个数对应于维卡在坐标 $X_i$ 处提出的问题的答案。所有答案均对 $M$ 取模后输出。

In the first sample, to make the stone touch the water at a point with coordinate $2$, it needs to be thrown with a force of $2$. To make the stone touch the water at a point with coordinate $2 \cdot 3 = 6$, it needs to be thrown with a force of $3$ or $6$.

In the second sample, you can skim a stone with a force of $5$ or $14$ to make it touch the water at a point with coordinate $7 \cdot 2 = 14$. For the coordinate $14 \cdot 13 = 182$, there are $4$ possible forces: $20$, $29$, $47$, $182$.

在第一个样例中，要使石子在坐标为 $2$ 的点处触水，需要以力 $2$ 投掷；要使石子在坐标为 $2 \cdot 3 = 6$ 的点处触水，需要以力 $3$ 或 $6$ 投掷。

在第二个样例中，可以以力 $5$ 或 $14$ 打水漂，使石子在坐标为 $7 \cdot 2 = 14$ 的点处触水；对于坐标 $14 \cdot 13 = 182$，存在 $4$ 种可能的力：$20$、$29$、$47$、$182$。