310539: CF1848E. Vika and Stone Skipping

E. Vika and Stone Skippingtime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

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

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

ExamplesInput

1 2 179
2 3

Output

1
2

Input

7 5 998244353
2 13 1 44 179

Output

2
4
4
8
16

Input

1000000000 10 179
58989 49494 8799 9794 97414 141241 552545 145555 548959 774175

Output

120
4
16
64
111
43
150
85
161
95

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

题目大意：
在维卡的家乡符拉迪沃斯托克，有一个美丽的大海。孩子们经常玩跳石游戏，即以小角度向大海投掷石头，使石头飞得远并在水面上弹跳多次。如果以力f从岸边垂直于海岸线投掷石头，它首先会在距离岸边f的地方接触水面，然后弹起并在距离前一次接触点f-1的地方再次接触水面。石头将继续直线飞行，直到落水。

形式上，石头接触水面的点的坐标将是：f, f+(f-1), f+(f-1)+(f-2), ..., f+(f-1)+(f-2)+...+1（假设0是岸线的坐标）。

维卡想知道，有多少个不同的力f_i可以使n块石头在坐标为x的点接触水面，并且所有的f_i都是不同的正整数。维卡还想知道，如果将坐标x乘以一些正整数x_1, x_2, ..., x_q，她的答案会如何变化。

输入输出数据格式：
输入：
第一行包含三个整数x (1≤x≤10^9), q (1≤q≤10^5) 和 M (100≤M≤2×10^9) —— 维卡自己回答问题的初始坐标，维卡将用来乘以初始坐标的整数x_i的数量，以及素数模M。
第二行包含q个整数x_1, x_2, x_3, ..., x_q（1≤x_i≤10^6）—— 上述描述的整数。

输出：
输出q个整数，其中第i个数对应于维卡对坐标X_i的问题的答案。输出所有答案模M。

示例：
输入：
1 2 179
2 3
输出：
1
2

输入：
7 5 998244353
2 13 1 44 179
输出：
2
4
4
8
16

输入：
1000000000 10 179
58989 49494 8799 9794 97414 141241 552545 145555 548959 774175
输出：
120
4
16
64
111
43
150
85
161
95

注意：
在第一个示例中，要使石头在坐标为2的点接触水面，需要以力2投掷。要使石头在坐标为2*3=6的点接触水面，需要以力3或6投掷。
在第二个示例中，可以以力5或14使石头在坐标为7*2=14的点接触水面。对于坐标14*13=182，有4个可能的力：20, 29, 47, 182。题目大意： 在维卡的家乡符拉迪沃斯托克，有一个美丽的大海。孩子们经常玩跳石游戏，即以小角度向大海投掷石头，使石头飞得远并在水面上弹跳多次。如果以力f从岸边垂直于海岸线投掷石头，它首先会在距离岸边f的地方接触水面，然后弹起并在距离前一次接触点f-1的地方再次接触水面。石头将继续直线飞行，直到落水。 形式上，石头接触水面的点的坐标将是：f, f+(f-1), f+(f-1)+(f-2), ..., f+(f-1)+(f-2)+...+1（假设0是岸线的坐标）。 维卡想知道，有多少个不同的力f_i可以使n块石头在坐标为x的点接触水面，并且所有的f_i都是不同的正整数。维卡还想知道，如果将坐标x乘以一些正整数x_1, x_2, ..., x_q，她的答案会如何变化。 输入输出数据格式： 输入： 第一行包含三个整数x (1≤x≤10^9), q (1≤q≤10^5) 和 M (100≤M≤2×10^9) —— 维卡自己回答问题的初始坐标，维卡将用来乘以初始坐标的整数x_i的数量，以及素数模M。 第二行包含q个整数x_1, x_2, x_3, ..., x_q（1≤x_i≤10^6）—— 上述描述的整数。 输出： 输出q个整数，其中第i个数对应于维卡对坐标X_i的问题的答案。输出所有答案模M。 示例： 输入： 1 2 179 2 3 输出： 1 2 输入： 7 5 998244353 2 13 1 44 179 输出： 2 4 4 8 16 输入： 1000000000 10 179 58989 49494 8799 9794 97414 141241 552545 145555 548959 774175 输出： 120 4 16 64 111 43 150 85 161 95 注意： 在第一个示例中，要使石头在坐标为2的点接触水面，需要以力2投掷。要使石头在坐标为2*3=6的点接触水面，需要以力3或6投掷。 在第二个示例中，可以以力5或14使石头在坐标为7*2=14的点接触水面。对于坐标14*13=182，有4个可能的力：20, 29, 47, 182。