#define MOD 76543int hs[MOD],head[MOD],next[MOD],id[MOD],top;void insert(int x,int y){    int k = x%MOD;    hs[top] = x, id[top] = y, next[top] = head[k], head[k] = top++;}int find(int x){    int k = x%MOD;    for(int i = head[k]; i != -1; i = next[i])        if(hs[i] == x)            return id[i];    return -1;}int BSGS(int a,int b,int n){    memset(head,-1,sizeof(head));    top = 1;    if(b == 1)return 0;    int m = sqrt(n*1.0), j;    long long x = 1, p = 1;    for(int i = 0; i < m; ++i, p = p*a%n)insert(p*b%n,i);    for(long long i = m; ;i += m)    {        if( (j = find(x = x*p%n)) != -1 )return i-j;        if(i > n)break;    }    return -1;}

const int  MAXN= 99991 ;struct LINK{    ll data;    ll j;    ll next;}HASH_LINK[1000000];ll ad, head[MAXN];ll Gcd(ll a, ll b){return b ? Gcd(b, a % b) : a;}ll Ext_Gcd(ll a, ll b, ll &x, ll &y){    if(!b){       x = 1; y = 0;       return a;    }    ll r = Ext_Gcd(b, a % b, x, y);    ll t = x; x = y; y = t - a / b * y;    return r;}ll POWER(ll a, ll b, ll c){    ll ans = 1;    while(b){       if(b & 1) ans = ans * a % c;       a = a * a % c;       b >>= 1;    }    return ans;}void init(){    memset(head, -1, sizeof(head));    ad = 0;}ll Hash(ll a){    return a % MAXN;}void INSERT_HASH(ll i, ll buf){    ll hs = Hash(buf), tail;    for(tail = head[hs]; ~tail; tail = HASH_LINK[tail]. next)       if(buf == HASH_LINK[tail]. data) return;    HASH_LINK[ad]. data = buf;    HASH_LINK[ad]. j    = i;    HASH_LINK[ad]. next = head[hs];    head[hs] = ad ++;}ll BSGS(ll a, ll b, ll c){    ll i, buf, m, temp, g, D, x, y, n = 0;    for(i = 0, buf = 1; i < 100; i ++, buf = buf * a % c)       if(buf == b) return i;    D = 1;    while((g = Gcd(a, c)) != 1){       if(b % g) return -1; // g | b 不满足，则说明无解       b /= g;       c /= g;       D = D * a / g % c;       ++ n;    }    init();    m = ceil(sqrt((long double) c));    for(i = 0, buf = 1; i <= m; buf = buf * a % c, i ++) INSERT_HASH(i, buf);    for(i = 0, temp = POWER(a, m, c), buf = D; i <= m; i ++, buf = temp * buf % c){       Ext_Gcd(buf, c, x, y);       x = ((x * b) % c + c) % c;       for(ll tail = head[Hash(x)]; ~tail; tail = HASH_LINK[tail].next)           if(HASH_LINK[tail]. data =http://www.mamicode.com/= x) return HASH_LINK[tail].j + n + i * m;    }    return -1;}