小A与两位神仙

题目背景

小A是一个普普通通的高中生,但是他某一天忽然被卷入了神仙的游戏中,快来帮帮他!

题目描述

某一天,小A正走在放学回家的路上,忽然遇见了两个神仙造梦者和杰瑞米,祂们一看到小A就说要和小A玩游戏,小A被笼罩在金光中,莫名其妙就答应了祂们的要求。 这个游戏的规则是这样的:两个神仙先选定一个正整数 $m$,保证 $m$ 是一个奇质数 $p$ 的正整数次幂。然后进行 $n$ 轮游戏,每轮中造梦者选定一个正整数 $x$,杰瑞米选定一个正整数 $y$,保证 $(x, m) = 1, (y, m) = 1$,即 $x$ 与 $m$ 互质,$y$ 与 $m$ 互质,接下来询问小A是否存在非负整数 $a$ 使得 $x^a \equiv y \pmod{m}$。 神仙们说小A只有在每一轮游戏中都回答正确才能回到正常的生活中,不得已之下他只好求助于聪明的你。

输入输出格式

输入格式


第一行两个正整数 $m, n$。 接下来 $n$ 行,每行两个正整数 $x, y$。

输出格式


一共 $n$ 行,每行对应一轮游戏中小A的回答。 如果存在,那么答案为 `Yes`,否则为 `No`。

输入输出样例

输入样例 #1

9 3
1 4
2 1
7 4

输出样例 #1

No
Yes
Yes

输入样例 #2

29788562298698657 10
4623623705787050 4128735493476588
29371111781967946 19402395181570597
23313713550468151 18155134012955455
654639695903289 323875358727922
15727861955653242 26658913688488667
10815360622718474 4625834559167483
10836636083182170 10347869939717751
8972909638986721 1887397472131862
23442032136521081 29735793306181382
325363900801763 6960017105353559

输出样例 #2

Yes
No
No
Yes
Yes
Yes
No
Yes
Yes
No

说明

**样例解释** $1^a \equiv 1 \not \equiv 4 \pmod {9}$。 $2^6 \equiv 64 \equiv 1 \pmod {9}$。 $7^2 \equiv 49 \equiv 4 \pmod {9}$。 **数据范围** 本题共 $7$ 个子任务,你需要通过一个子任务内的所有测试点才能取得这个子任务的分数。 对于所有数据满足 $1\le n\le 2\times 10^4, 3\le m \le 10^{18}, 1 \le x, y < m$ 。 | # | 分数 | $n$ | $m$ | 特殊性质1 | 时间限制 | | ---- | ---- | ------------------------ | ------------------- | --------- | --------- | | 1 | 3 | $\le 5$ | $\le 10^6$ | × | 1s | | 2 | 37 | $\le 5$ | $\le 10^9$ | × | 1s | | 3 | 22 | $= 1$ | $\le 10^{18}$ | × | 1s | | 4 | 13 | $\le 100$ | $\le 10^{18}$ | √ | 1s | | 5 | 10 | $\le 100$ | $\le 10^{18}$ | × | 1s | | 6 | 5 | $\le 2000$ | $\le 10^{18}$ | × | 1s | | 7 | 10 | $\le 2\times 10^4$ | $\le 10^{18}$ | × | 3s | 特殊性质1:令 $m = p^{a}$,则 $p$ 是在 $[3, 10^{18}]$ 等概率选取的一个素数。 **提示** 本题可以使用 `__int128`。