Vika and Stone Skipping
Contest: Codeforces Round 885 (Div. 2)
Difficulty rating: 2600
Tags: brute force, implementation, math, number theory

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.

Input format:
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.

Output format:
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$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
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$$$.

Example input:
1 2 179
2 3

Example output:
1
2

Example input:
7 5 998244353
2 13 1 44 179

Example output:
2
4
4
8
16

Editorial:
The key observation is that the answer for coordinate $$$x$$$ is the number of odd divisors of $$$x$$$. Let's prove this.
Let's see how far a pebble will fly with force $$$f$$$, which touches the water $$$cnt$$$ times: $$$f + (f - 1) + \ldots + (f - cnt + 1) = x$$$. If $$$cnt$$$ is even, then $$$x = (cnt / 2) \cdot (2 \cdot f - cnt + 1) = (p) \cdot (2 \cdot k + 1)$$$, where $$$p = cnt / 2, k = f - p$$$. In this case, the condition $$$f - cnt + 1 > 0$$$ is necessary, which is equivalent to $$$p \le k$$$.
If $$$cnt$$$ is odd, then $$$x = cnt \cdot (f - (cnt - 1) / 2) = (2 \cdot k + 1) \cdot (p)$$$, where $$$p = (f - (cnt - 1) / 2), k = (cnt - 1) / 2$$$. Thus, the necessary condition $$$f - cnt + 1 > 0$$$ is equivalent to $$$p > k$$$.
Therefore, for each odd divisor $$$2 \cdot k + 1$$$ of the number $$$x$$$, we can uniquely associate one of the decomposition options, and hence the number of possible answers is exactly equal to the number of different odd divisors in the factorization of the number $$$x$$$.
Using this observation, it is easy to obtain the answer. We will maintain the power of each prime number in the current coordinate. The answer is the product of (powers $$$+ 1$$$). In order to quickly understand how these quantities change, we will pre-calculate the factorization of all numbers from $$$1$$$ to $$$10^6$$$. Then the query can be processed by quickly recalculating the powers using the pre-calculated factorizations.