在维卡的家乡符拉迪沃斯托克,有一片美丽的大海。
你经常可以看到孩子们在偷石头。这是以小角度向海中扔一块石头,使其飞得很远并在水面上弹起数次的过程。
Vika 曾多次撇过石头,知道如果你以 $$$f$$$ 的力从海岸垂直于海岸线扔出一块石头,它会首先在距海岸 $$$f$$$ 的距离处接触水面,然后反弹并在距前一个接触点 $$$f - 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$$$、...、$$$x_q$$$(她选择这些正整数进行分析),问题的答案会如何变化。
Vika 发现自己很难应对此类分析,因此她向您寻求帮助。
正式地,Vika 对坐标 $$$X_1 = x \cdot x_1$$$, $$$X_2 = X_1 \cdot x_2$$$, ... , $$$X_q = X_{q-1} \cdot x_q$$$ 的问题的答案感兴趣。由于此类坐标的答案可能相当大,因此请对 $$$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 与初始坐标和质数模 $$$M$$$ 相乘的整数 $$$x_i$$$ 的数量。
输入的第二行包含 $$$q$$$ 整数 $$$x_1, x_2, x_3, \ldots, x_q$$$ ($$$1 \le x_i \le 10^6$$$) - 语句中描述的整数。
输出
输出 $$$q$$$ 整数,其中第 $$$i$$$ 个数字对应于 Vika 的坐标 $$$X_i$$$ 问题的答案。输出所有对 $$$M$$$ 取模的答案。
示例
输入 #1
1 2 179 2 3
输出 #1
1 2
输入 #2
7 5 998244353 2 13 1 44 179
输出 #2
2 4 4 8 16
输入 #3
1000000000 10 179 58989 49494 8799 9794 97414 141241 552545 145555 548959 774175
输出 #3
120 4 16 64 111 43 150 85 161 95
注意
在第一个示例中,要使石头在坐标为 $$$2$$$ 的点接触到水,需要用 $$$2$$$ 的力将其抛出。要使石头在坐标 $$$2 \cdot 3 = 6$$$ 的点接触到水,需要用 $$$3$$$ 或 $$$6$$$ 的力将其抛出。
在第二个示例中,您可以用 $$$5$$$ 或 $$$14$$$ 的力撇去一块石头,使其在坐标为 $$$7 \cdot 2 = 14$$$ 的点接触到水。对于坐标 $$$14 \cdot 13 = 182$$$,有 $$$4$$$ 可能的力:$$$20$$$、$$$29$$$、$$$47$$$、$$$182$$$。