编程题：防AK题
> $AK$ 即 $All~Killed$，意为通过所有题目。而众所周知，程序设计竞赛的传统艺能之一就是出一道巨难的题防止有选手 $AK$，因此便有了该题，同时也鼓励有一定基础的同学挑战一下。（能骗到分就算成功）
给你一个正整数 $m$，有 $q$ 次询问，每次询问给出两个正整数 $x,y$，问你是否存在一个非负整数 $a$，使得 $x^a\equiv y \pmod m$。
### 输入格式:
第一行给出两个正整数 $m$ 和 $q$。
接下来 $q$ 行，每行给出两个正整数 $x,y$。
保证 $m$ 是一个奇质数的正整数次幂，且 $gcd(x,m)=1,~gcd(y,m)=1$。
（$1\leq q \leq 2e4,~3\leq m\leq 1e18,~1\leq x,y\leq m$）
### 输出格式:
输出 $q$ 行，每行对应每个询问，如果存在，则输出“$YES$”，否则输出“$NO$”。（不带引号）
### 输入样例1:
in
11 3
5 7
8 9
6 4
### 输出样例1:
out
NO
YES
YES
### 输入样例2:
in
678223072849 8
5435345 654645
114514 1919810
7676555 23423424
54353455 54353455
1 1
543555 33333301
23333 66789
1000000009 1000000007
### 输出样例2:
out
NO
NO
NO
YES
YES
YES
YES
NO
### tips:
本题建议使用 __int128。
答案：若无答案欢迎评论
给你一个正整数 $m$，有 $q$ 次询问，每次询问给出两个正整数 $x,y$，问你是否存在一个非负整数 $a$，使得 $x^a\equiv y \pmod m$。
### 输入格式:
第一行给出两个正整数 $m$ 和 $q$。
接下来 $q$ 行，每行给出两个正整数 $x,y$。
保证 $m$ 是一个奇质数的正整数次幂，且 $gcd(x,m)=1,~gcd(y,m)=1$。
（$1\leq q \leq 2e4,~3\leq m\leq 1e18,~1\leq x,y\leq m$）
### 输出格式:
输出 $q$ 行，每行对应每个询问，如果存在，则输出“$YES$”，否则输出“$NO$”。（不带引号）
### 输入样例1:
in
11 3
5 7
8 9
6 4
### 输出样例1:
out
NO
YES
YES
### 输入样例2:
in
678223072849 8
5435345 654645
114514 1919810
7676555 23423424
54353455 54353455
1 1
543555 33333301
23333 66789
1000000009 1000000007
### 输出样例2:
out
NO
NO
NO
YES
YES
YES
YES
NO
### tips:
本题建议使用 __int128。
答案：若无答案欢迎评论