//author Eterna
#define Hello the_cruel_world!
#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<utility>
#include<cmath>
#include<climits>
#include<deque>
#include<functional>
#include<complex>
#include<numeric>
#include<unordered_map>
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define Pi acos(-1.0)
#define ABS(x) ((x) >= 0 ? (x) : (-(x)))
#define pb(x) push_back(x)
#define lowbit(x) (x & -x)
#define FRIN freopen("C:\\Users\\Administrator.MACHENI-KA32LTP\\Desktop\\in.txt", "r", stdin)
#define FROUT freopen("C:\\Users\\Administrator.MACHENI-KA32LTP\\Desktop\\out.txt", "w", stdout)
#define FAST ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define outd(x) printf("%d\n", x)
#define outld(x) printf("%lld\n", x)
#define il inline
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int maxn = 1e5;
const int INF = 0x7fffffff;
const int mod = 1e9 + 7;
const double eps = 1e-7;
inline int read_int() {
char c;
int ret = 0, sgn = 1;
do { c = getchar(); } while ((c < '0' || c > '9') && c != '-');
if (c == '-') sgn = -1; else ret = c - '0';
while ((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + (c - '0');
return sgn * ret;
}
inline ll read_ll() {
char c;
ll ret = 0, sgn = 1;
do { c = getchar(); } while ((c < '0' || c > '9') && c != '-');
if (c == '-') sgn = -1; else ret = c - '0';
while ((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + (c - '0');
return sgn * ret;
}
inline ll Quick_pow(ll a, ll b, int p) {
ll res = 1;
while (b) {
if (b & 1) (res *= a) %= p;
(a *= a) %= p;
b >>= 1;
}
return res;
}
ll extend_gcd(ll a, ll b, ll& x, ll& y) {
ll d = a;
if (b != 0) {
d = extend_gcd(b, a % b, y, x);
y -= (a / b) * x;
}
else x = 1, y = 0;
return d;
}
map<ll, int> mp;
int BSGS(ll y, ll z, ll p) {
if (y == 0 && z == 0) return 1;
if (y == 0 && z != 0) return -1;
int m = sqrt(p);
mp.clear();
int t = z % p;
mp[t] = 0;
for (int j = 1; j <= m; j++) {
t = t*y%p;
mp[t] = j;
}
t = 1;
ll mi = Quick_pow(y, m, p), x;
for (int i = 1; i*i <= p + 1; i++) {
t = t * mi % p;
if (mp.count(t)) {
x = i*m - mp[t];
return (x % p + p) % p;
}
}
return -1;
};