题目描述

在Vika的家乡海参崴，有一个美丽的海洋。

经常可以看到孩子们扔石头。这是将石头以一个小角度从岸边向海洋扔出去，使其飞行很远并且在水面上连续弹跳几次的过程。

Vika经常扔石头，她知道如果从与海岸线垂直的方向用力扔出一块石头，它会首先在离岸边 $f$ 的位置触及水面，然后弹起并在距离前一次接触点 $f - 1$ 的位置再次触及水面。石头会继续直线飞行，减小接触水面点之间的距离，直到掉入海洋。

具体来说，石头接触水面的点的坐标依次为：$f$ ，$f + (f - 1)$ ，$f + (f - 1) + (f - 2)$ ，... ，$f + (f - 1) + (f - 2) + \ldots + 1$ （假设岸边坐标为0）。

有一天，当Vika在傍晚沿着海参崴的堤坝散步时，她看到了一群男孩们从同一点向海洋扔石头，他们用不同的力量扔石头。

她对于最多可以有多少个男孩以他们的力量 $f_i$ 扔出一块石头，使得所有的 $f_i$ 都是不同的正整数，并且所有的 $n$ 块石头都在坐标为 $x$ 的位置接触水面感兴趣。

经过一番思考后，Vika回答了自己的问题。之后，她开始分析如果将坐标 $x$ 乘以一些正整数 $x_1$ ，$x_2$ ，... ，$x_q$ ，她选定的用于分析的数。

Vika很难自己进行这种分析工作，所以她求助于你的帮助。

具体来说，对于坐标 $X_1 = x \cdot x_1$ ，$X_2 = X_1 \cdot x_2$ ，... ，$X_q = X_{q-1} \cdot x_q$ ，Vika想知道对于这些坐标她问题的答案。由于这些答案可能很大，所以请对模 $M$ 取余。保证 $M$ 是一个质数。

输入格式

输入的第一行包含三个整数 $x$ （ $1 \le x \le 10^9$ ），$q$ （ $1 \le q \le 10^5$ ），$M$ （ $100 \le M \le 2 \cdot 10^9$ ）——Vika自己回答问题的初始坐标、Vika将要分析的整数 $x_i$ 的个数和质数模 $M$ 。

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

输出格式

输出 $q$ 个整数，其中第 $i$ 个数字对应于Vika对于坐标 $X_i$ 的问题的答案。对所有答案进行模 $M$ 的运算。

提示 在第一个样例中，为了使石头在坐标为2的位置接触到水面，需要用力抛出石头的力量为2。为了使石头在坐标为 $2 \cdot 3 = 6$ 的位置接触到水面，需要用力抛出石头的力量为3或6。

在第二个样例中，你可以用力5或14将石头扔到坐标为7的位置接触水面。对于坐标为14的位置，有4种可能的力量：20，29，47，182。