#include<bits/stdc++.h>
#define N 114514
#define Np 1919810
#define int long long
using namespace std;
bool ok[Np];
int i,j,tot,ans1,ans2;
int primes[Np],phi[Np],mu[Np];
unordered_map<int,int>mp;
int gcd(int a,int b)
//最大公约数 
{
    return b?gcd(b,a%b):a;
}
int lcm(int a,int b)
//最小公倍数 
{
    return a*b/gcd(a,b);
}
int read()
//快读
{
    char c=getchar();
    int flag=1,ans=0;
    while(c<'0'||c>'9')
    {
        if(c=='-')  flag=0;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        ans=ans*10+(c^48);
        c=getchar();
    }
    return flag?ans:-ans;
}
void write(int x)
//快写
{
    if(x>9) write(x/10);
    putchar(x%10+'0');
    return ;
}
int pow_mod(int a,int b,int p)
//快速幂 
{
    int ans=1;
    while(b)
    {
        if(b&1) ans=a*ans%p;
        a=a*a%p;
        b>>=1;
    }
    return ans;
}
int time_mod(int a,int b,int p)
//龟速乘 
{
    int ans=0;
    while(b)
    {
        if(b&1) ans=(ans+a)%p;
        a=(a*2)%p;
        b>>=1;
    }
    return ans;
}
void exgcd(int a,int b)
//同余方程ax≡1(modb)，其中ans1是特解 
{
    if(!b)
    {
        ans1=1;
        ans2=0;
        return ;
    }
    exgcd(b,a%b);
    swap(ans1,ans2);
    ans2-=a/b*ans1;
    return ;
}
void mu_all()
//求出1~N中所有的mu(i) 
{
    mu[1]=1;
    for(int i=2;i<=N;i++)   ok[i]=1;
    for(int i=2;i<=N;i++)
    {
        if(ok[i])
        {
            primes[++tot]=i;
            mu[i]=-1;
        }
        for(int j=1;i*primes[j]<=N;j++)
        {
            ok[i*primes[j]]=0;
            if(i%primes[j]==0)  break;
            mu[i*primes[j]]=-mu[i];
        }
    }
    return ;
}
void phi_all() 
//求出1~N中所有的phi(i) 
{
    phi[1]=1;
    for(int i=2;i<=N;i++)   ok[i]=1;
    for(int i=2;i<=N;i++)
    {
        if(!ok[i])
        {
            primes[++tot]=i;
            phi[i]=i-1;
        }
        for(int j=1;primes[j]*i<=N;j++)
        {
            ok[primes[j]*i]=1;
            if(i%primes[j]==0)
            {
                phi[primes[j]*i]=phi[i]*primes[j];
                break;
            }
            phi[primes[j]*i]=phi[i]*(primes[j]-1);
        }
    }
    return ;
}
int phi_one(int x)
//求出mu(x) 
{
    int ans=x;
    for(i=1;i<=tot&&primes[i]*primes[i]<=x;i++)
    {
        if(ans%primes[i]==0)
        {
            ans=ans/primes[i]*(primes[i]-1);
            while(x%primes[i]==0)   x/=primes[i];
        }
    }
    if(x>1) ans=ans/x*(x-1);
    return ans;
}
int bsgs(int a,int b,int p,int num)
//baby step giant step(simpler)
{
    mp.clear();
    int m=ceil(sqrt(p)),s=1;
    for(int i=0;i<m;i++,s=s*a%p)    mp[s*b%p]=i;
    int temp=s;
    s=num;
    for(int i=0;i<=m;i++,s=s*temp%p)    if(mp.find(s)!=mp.end()&&i*m-mp[s]>=0)  return i*m-mp[s];
    return -1;
}
int exbsgs(int a,int b,int p)
//baby step giant step
{
    a%=p;
    b%=p;
    if(p==1||b==1)  return 0;
    int d,cnt=0,qwq=1;
    while((d=gcd(a,p))^1)
    {
        if(b%d) return -1;
        cnt++;
        b/=d;
        p/=d;
        qwq=(qwq*a/d)%p;
        if(qwq==b)  return cnt;
    }
    int ans=bsgs(a,b,p,qwq);
    if(!~ans)   return -1;
    else    return ans+cnt;
}
main()
{
    return 0;
}