QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#32541#870. HackermanFroggyguaAC ✓46ms68996kbC++1710.8kb2022-05-21 10:33:442023-01-15 18:28:34

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-15 18:28:34]
  • Judged
  • Verdict: AC
  • Time: 46ms
  • Memory: 68996kb
  • [2022-05-21 10:33:44]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
namespace Get_cir{
	map<pair<int,int>,int> mp;
	int mod;
	pii base;
	inline pii operator * (const pii &a,const pii &b){
		return pii(1LL*a.first*b.first%mod,(1LL*a.second*b.first+b.second)%mod);
	}
	int calc(int _mod,pii _base){
		mod=_mod,base=_base;
		mp.clear();
		pii u(1,0);
		mp[u]=0;
		for(int i=1;;++i){
			u=u*base;
			if(mp.count(u)){
				//cerr<<" jk! "<<mp[u]<<" "<<i<<endl;
				return i;
				break;
			}
		}
	}
}
enum multiply_tag{
    brute_tag,fft_tag,mix_tag
};
struct Complex{
    double x,y;
    Complex(double _x=0,double _y=0){x=_x,y=_y;}
    friend Complex operator + (const Complex &a,const Complex &b){
        return Complex(a.x+b.x,a.y+b.y);
    }
    friend Complex operator - (const Complex &a,const Complex &b){
        return Complex(a.x-b.x,a.y-b.y);
    }
    friend Complex operator * (const Complex &a,const Complex &b){
        return Complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);
    }
};
template<int L>
class Poly_fft{
    using poly=Poly_fft<L>;
    static constexpr double PI=acos(-1.0);
    vector<Complex> f;
    struct initializer{
        vector<Complex> GG[2][L+1];
        initializer(){
            for(int p=1;p<=L;++p){
                Complex buf1(cos(2*PI/(1<<p)),sin(2*PI/(1<<p)));
                Complex buf0(cos(2*PI/(1<<p)),-sin(2*PI/(1<<p)));
                GG[0][p].resize(1<<p);
                GG[1][p].resize(1<<p);
                GG[0][p][0]=GG[1][p][0]=Complex(1,0);
                for(int i=1;i<(1<<p);++i){
                    GG[0][p][i]=GG[0][p][i-1]*buf0;
                    GG[1][p][i]=GG[1][p][i-1]*buf1;
                }
            }
        }
    };
    static initializer init;
    static vector<int> tr;
    static int FFT_init(int n){
        int lim=1;
        while(lim<n)lim<<=1;
        tr.resize(lim);
        for(int i=0;i<lim;++i){
            tr[i]=((tr[i>>1]>>1)|(i&1?lim>>1:0));
        }
        return lim;
    }
    static void FFT(poly &A,int flag,int n){
        A.resize(n);
        for(int i=0;i<n;++i){
            if(i<tr[i])swap(A.f[i],A.f[tr[i]]);
        }
        for(int p=2,j=1;p<=n;p<<=1,++j){
            int len=p>>1;
            for(int k=0;k<n;k+=p){
                auto buf=init.GG[flag][j].begin();
                for(int i=k;i<k+len;++i,++buf){
                    Complex tmp=(*buf)*A.f[i+len];
                    A.f[i+len]=A.f[i]-tmp;
                    A.f[i]=A.f[i]+tmp;  
                }
            }   
        }
        if(!flag){
            for(int i=0;i<n;++i){
                A.f[i].x=A.f[i].x/n;
            }   
        }
    }
public:
    Poly_fft(const vector<Complex> &_f):f(_f){}
    Poly_fft(){}
    Poly_fft(int _n){f.resize(_n);}
    int size(){return f.size();}
    void resize(int _n){f.resize(_n);}
    vector<Complex>::reference operator [] (int x){
        return f[x];
    }
    friend poly Mul(poly A,poly B){
        int n=A.size()+B.size()-1;
        int lim=FFT_init(n);
        poly C(lim);
        FFT(A,1,lim),FFT(B,1,lim);
        for(int i=0;i<lim;++i){
            C[i]=A[i]*B[i];
        }
        FFT(C,0,lim);
        C.resize(n);
        return C;
    }
};
template<int L>
typename Poly_fft<L>::initializer Poly_fft<L>::init;
template<int L>
vector<int> Poly_fft<L>::tr;
using poly=Poly_fft<20>;
/*
进制,压位长度,乘法方式
*/
template<int H,int D,multiply_tag mtag>          
class unsigned_bigint{
    using bint=unsigned_bigint<H,D,mtag>;
    static constexpr int B=round(pow(H,D));
    vector<int> g;
public:
    unsigned_bigint(const vector<int> &_g):g(_g){}
    unsigned_bigint(int x=0){
        if(!x){g.resize(1);return;}
        while(x)g.push_back(x%B),x/=B;  
    }
    unsigned_bigint(string s){
        g.resize(((int)s.length()+D-1)/D);
        reverse(s.begin(),s.end());
        for(int i=0;i*D<(int)s.length();++i){
            for(int j=min(D,(int)s.length()-i*D)-1;j>=0;--j){
                g[i]=g[i]*H+s[i*D+j]-'0';
            }
        }   
    }
    int length(){
        int len=D*(g.size()-1);
        int x=g.back();
        while(x)x/=H,++len;
        return max(1,len);
    }
    void Del(){
        g.pop_back();
        if(g.empty())g.push_back(0);
    }
    bint &operator += (const bint &b){
        if(b.g.size()>g.size())g.resize(b.g.size());
        g.push_back(0);
        for(int i=0;i<(int)g.size();++i){
            if(i<(int)b.g.size())g[i]+=b.g[i];
            if(g[i]>=B)++g[i+1],g[i]-=B;    
        }
        while(g.size()>1&&!g.back())g.pop_back();
        return *this;
    }
    bint &operator -= (const bint &b){
        if(b.g.size()>g.size())g.resize(b.g.size());
        g.push_back(0);
        for(int i=0;i<(int)g.size();++i){
            if(i<(int)b.g.size())g[i]-=b.g[i];
            if(g[i]<0)--g[i+1],g[i]+=B; 
        }
        while(g.size()>1&&!g.back())g.pop_back();
        return *this;
    }
    bint &operator *= (const bint &b){
        vector<ll> tmp;
        if(mtag==brute_tag||(mtag==mix_tag&&1LL*g.size()*b.g.size()<=1e7)){
            tmp.resize(g.size()+b.g.size());
            for(int i=0;i<(int)g.size();++i){
                for(int j=0;j<(int)b.g.size();++j){
                    tmp[i+j]+=1LL*g[i]*b.g[j];  
                }
            }
            g.resize(g.size()+b.g.size());
        }
        else{
            poly F(g.size()),G(b.g.size());
            for(int i=0;i<(int)F.size();++i)F[i].x=g[i];
            for(int i=0;i<(int)G.size();++i)G[i].x=b.g[i];
            F=Mul(F,G);
            g.resize(F.size()+1);
            tmp.resize(F.size()+1);
            for(int i=0;i<(int)F.size();++i){
                tmp[i]=round(F[i].x);
            }
        }
        for(int i=0;i<(int)tmp.size();++i){
            g[i]=tmp[i]%B;
            if(tmp[i]>=B)tmp[i+1]+=tmp[i]/B;
        }
        while(g.size()>1&&!g.back())g.pop_back();
        return *this;
    }
    bint &operator /= (const bint &b){
        if(b.g.size()>g.size()){
            g=vector<int>(1);
        }
        else{
            bint a;
            a.g.resize(g.size()-b.g.size()+1);
            for(int i=g.size()-b.g.size();i>=0;--i){
                bint tmp(vector<int>(g.begin()+i,g.end()));
                g.erase(g.begin()+i,g.end());
                int l=0,r=B;
                while(l<r){
                    int mid=(l+r)>>1;
                    if(bint(mid)*b<=tmp){
                        a.g[i]=mid;
                        l=mid+1;
                    }
                    else{
                        r=mid;
                    }
                }
                tmp-=a.g[i]*b;
                if(tmp>bint(0))g.insert(g.end(),tmp.g.begin(),tmp.g.end());
            }
            g=a.g;
            while(g.size()>1&&!g.back())g.pop_back();
            /*
            bint a;
            a.g.resize(g.size()-b.g.size()+1);
            for(int i=g.size()-b.g.size();i>=0;--i){
                bint tmp(vector<int>(g.begin()+i,g.end()));
                g.erase(g.begin()+i,g.end());
                while(tmp>=b){
                    tmp-=b,++a.g[i];
                }
                if(tmp>bint(0))g.insert(g.end(),tmp.g.begin(),tmp.g.end());
            }
            g=a.g;
            while(g.size()>1&&!g.back())g.pop_back();
            */
        }
        return *this;
    }
    bint &operator %= (const bint &b){
        (*this)=(*this)-(*this)/b*b;
        return *this;
    }
    bint Pow(int b){
        bint ans(1);
        int k=0;
        while(b>=(1<<k))++k;
        for(int i=k-1;i>=0;--i){
            ans=ans*ans;
            if(b>>i&1)ans=ans*(*this);
        }
        return ans;
    }
    friend bint operator + (const bint &a,const bint &b){
        return bint(a)+=b;
    }
    friend bint operator - (const bint &a,const bint &b){
        return bint(a)-=b;
    }
    friend bint operator * (const bint &a,const bint &b){
        return bint(a)*=b;
    }
    friend bint operator / (const bint &a,const bint &b){
        return bint(a)/=b;
    }
    friend bint operator % (const bint &a,const bint &b){
        return bint(a)%=b;
    }
    friend bool operator == (const bint &a,const bint &b){
        return a.g==b.g;
    }
    friend bool operator != (const bint &a,const bint &b){
        return !(a.g==b.g);
    }
    friend bool operator < (const bint &a,const bint &b){
        if(a.g.size()<b.g.size())return true;
        if(a.g.size()>b.g.size())return false;
        for(int i=a.g.size()-1;i>=0;--i){
            if(a.g[i]<b.g[i])return true;
            if(a.g[i]>b.g[i])return false;
        }
        return false;
    }
    friend bool operator > (const bint &a,const bint &b){
        return b<a;
    }
    friend bool operator <= (const bint &a,const bint &b){
        return !(a>b);
    }
    friend bool operator >= (const bint &a,const bint &b){
        return !(a<b);
    }
    friend ostream &operator << (ostream &out,const bint &a){
        string s="";
        if(!a.g.back())s="0";
        else{
            int x=a.g.back();
            while(x)s+=x%10+'0',x/=10;
            reverse(s.begin(),s.end());
        }
        out<<s;
        for(int i=(int)a.g.size()-2;i>=0;--i){
            s="";
            int x=a.g[i];
            for(int j=0;j<D;++j){
                s+=x%10+'0',x/=10;
            }
            reverse(s.begin(),s.end());
            out<<s; 
        }
        return out;
    }
};
using bint=unsigned_bigint<10,1,mix_tag>;
ll u,v;
bint Ask(ll x){
	cout<<"? "<<x<<endl;
	string s;
	cin>>s;
	return bint(s);
}
void exgcd(ll a,ll b,ll &x,ll &y){
	if(b==0){
		x=1,y=0;
		return;
	}
	exgcd(b,a%b,y,x);
	y-=a/b*x;
}
bint Get1(ll A,ll u,ll v,ll B,ll C){
	ll t=u%A;
	while(t%B==u%B||t%B==v%B||t%C==u%C||t%C==v%C){
		t+=A;
	}
	return Ask(t);
}
bint Get2(ll A,ll B,ll u,ll v,ll C){
	ll x,y;
	exgcd(A,B,x,y);
	ll c=((v-u)%B+B)%B;
	x=x*c%B;
	ll Lcm=A*B;
	ll t=(u+x*A)%Lcm;
	t=(t%Lcm+Lcm)%Lcm;
	while(t%C==u%C||t%C==v%C)t+=Lcm;
	return Ask(t);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	vector<int> A,p;
	A.push_back(Get_cir::calc(611953,pii(11,7)));
	A.push_back(Get_cir::calc(746773,pii(13,5)));
	A.push_back(Get_cir::calc(882389,pii(53,3)));
	cin>>u>>v;
	vector<bint> su(3),sv(3);
	bint X=Ask(u),Y=Ask(v);
	for(int i=0;i<3;++i){
		if(u%A[i]==v%A[i]){
			bint t=Get1(A[i],u,v,A[(i+1)%3],A[(i+2)%3]);
			su[i]=__gcd(X,t);
			sv[i]=__gcd(Y,t);
		}
		else{
			p.push_back(i);
		}
	}
	for(int i=0;i<p.size();++i){
		int j=(i+1)%p.size();
		bint t=Get2(A[p[i]],A[p[j]],u,v,A[p[i]^p[j]^3]);
		su[p[i]]=__gcd(X,t);
		sv[p[j]]=__gcd(Y,t);
	}
	cout<<"! "<<su[0]+su[1]+su[2]+sv[0]+sv[1]+sv[2]<<endl;
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 17ms
memory: 68644kb

input:

10 20
192279309409462992645482090330404758368400469722499925076043266903464961794187094077107243967491
274848544065337166381629952590164863776020394941410553373502453263042134278227621768923600557617
506096352633800802021638751293707660624503041064291938392086928726801805924681599525227548282533
576...

output:

? 10
? 20
? 1950444022
? 3913458676
? 140978462
! 1188670725123074098790368447122696

result:

ok Correct answer

Test #2:

score: 100
Accepted
time: 44ms
memory: 68856kb

input:

37 46
97825519574754092153758387764912275619234891313147117467743258182476235237292351844700364719169
54303479370678087384920399234466253444862272872172834147853150374135382664698264673080288884093
50233678594067149512057752145622885563364124208844922426023126492406191765427653393764870997607
366413...

output:

? 37
? 46
? 803340025
? 1832516294
? 386485981
! 886280847479253535234185813090550

result:

ok Correct answer

Test #3:

score: 100
Accepted
time: 23ms
memory: 68876kb

input:

44 8
139998480092642783417587715247058481747320544406167717972219233927730332587277433697128761470667
271152087704853858846849144773423085565311346795675002902335520211991422443533270376970737358031
58288433170657941476491574714892846730728452692307174479834123474745157615100697308848769680757
31089...

output:

? 44
? 8
? 1546938206
? 1117917728
? 1050109640
! 1381886467818751218186881323029526

result:

ok Correct answer

Test #4:

score: 100
Accepted
time: 12ms
memory: 68676kb

input:

82 68
188554949935264064678776197510968364875496054781466439374107711197781451374401747633705271089439
29581658567305216205082048469677895960082426925692604115399506310299669924186163606457155314301
75366448259556931974867632655700324034038750328933058158780711781659402833769015529256514177743
61514...

output:

? 82
? 68
? 601587145
? 434745848
? 841051598
! 1196634362150800601617401838757468

result:

ok Correct answer

Test #5:

score: 100
Accepted
time: 22ms
memory: 68676kb

input:

6996 5792
67390022391769391147714174495294677922764805779855130049980027749475287578218791727016463145831
190199098475228480278266091225461209267710398512722346092004924897055917999060793536265245866759
35471551009262696428028264471582880821261733714596282940127909262057696267458178347773969864937
2...

output:

? 6996
? 5792
? 1753364217
? 3596212024
? 2236996328
! 1573877234916808262400484435398174

result:

ok Correct answer

Test #6:

score: 100
Accepted
time: 20ms
memory: 68648kb

input:

3291 6445
54077827831440054267656259085398546500693356922505492053613106897329930710120182867932080538157
98201039695845250970300371144288835197672318177269114670062390258285188625955203446462917390277
94264603146478479313817557733724136936894074455322016030431950005524622905350104714574451011041
22...

output:

? 3291
? 6445
? 139528347
? 3433785409
? 1889331751
! 823431540819423718040224182607950

result:

ok Correct answer

Test #7:

score: 100
Accepted
time: 32ms
memory: 68720kb

input:

6536 5601
273599690267473575441266779803329986773862552397745534605008980423728022985536076633761206223031
156553040057872461907988875539888438079419984936293448076135238819105759558185107051162266052811
408937789777463127575758959318495732982811444726282048089465320013099215363881955262164756961933...

output:

? 6536
? 5601
? 904968803
? 1578869237
? 1096814820
! 992834514869972328760460805894386

result:

ok Correct answer

Test #8:

score: 100
Accepted
time: 28ms
memory: 68724kb

input:

3052 4062
59574401894516890937667534231902387085142553055840275586807209737178755702430565544589840466487
296512258026557361923772900048359250214321615908774409860481069059866462678653682063649352703999
269766965952195936464698525921920577562065095483209526505134385054947953901742103127363276030293
...

output:

? 3052
? 4062
? 1822625590
? 2428132210
? 1258559844
! 1133386155345044938400896772510646

result:

ok Correct answer

Test #9:

score: 100
Accepted
time: 22ms
memory: 68748kb

input:

2991535 6681913
102329449590046183323344211216588078072166766840184965814381413975903255392300460303709193660829
330348874670800743159006181681366540512786384932812621232039970043718708269944554728671291327553
192869545848754964297572235338141055512499059658977717652845820915950426710553587100724640...

output:

? 2991535
? 6681913
? 29458459
? 2811725489
? 1990400815
! 1453060498084516811315877375353214

result:

ok Correct answer

Test #10:

score: 100
Accepted
time: 34ms
memory: 68784kb

input:

9726238 6877918
589387736187305335574520273294597698164140932458000553468087261251075313297441776897965004482847
18779897395624462249194864702459285620828509776318474004688900021001021133252452155403252253129
2329893179368959780696531229266678092158831328766224868902064887997878634193380091197263024...

output:

? 9726238
? 6877918
? 1732294624
? 3501881034
? 588844270
! 1206601397235349945074775565671544

result:

ok Correct answer

Test #11:

score: 100
Accepted
time: 40ms
memory: 68716kb

input:

7959578 4047401
95053938326737316266379445586202057910211242713589662088704085467691737640008981600797306083983
49795741366721729385373098164984583424703870719972940250603216863378178756906319636085914616897
32924643564081539466779148165231427293748641617130899248797325010917896674934603461680184610...

output:

? 7959578
? 4047401
? 1869670550
? 1789321953
? 1713344078
! 925097705087720494776837821836552

result:

ok Correct answer

Test #12:

score: 100
Accepted
time: 23ms
memory: 68680kb

input:

1256557 4455761
238681085596282475937506347840070769465263961322040790391335315083915661919731893116613831535629
78529459861840340884641526948023676229894459303149924455130394075003661177738785095605838942897
1114179117878889050739363916526253527390996019657573045518015885845003593765177120199828104...

output:

? 1256557
? 4455761
? 1240612345
? 2535551801
? 2206412045
! 1356950779430279454530942638873694

result:

ok Correct answer

Test #13:

score: 100
Accepted
time: 38ms
memory: 68808kb

input:

5067300 4926563
228859205217244636912852630567243230052813454757650406883317445468737770247115670640960190511363
201484808844400742672954269627698861286759841465305062699604225148024203464672160265635695056467
260569742355201127452102632761145568114392510919131268993061067717083720784625886761004366...

output:

? 5067300
? 4926563
? 776279808
? 629928771
? 1118640956
! 990181739222037127397475513887002

result:

ok Correct answer

Test #14:

score: 100
Accepted
time: 25ms
memory: 68668kb

input:

3555743 7944318
82285827099855956956472351004449798422948581018031029475195444150521638632593622798977048932111
55724890135122649605027180487108321656326297217535846319578741826448763727493026873984774006863
18802799553673785322826233295081802977374391229712601635051363085629180243093232927609224062...

output:

? 3555743
? 7944318
? 1121630294
? 1148668374
? 1608619515
! 868402917169588784171188548644790

result:

ok Correct answer

Test #15:

score: 100
Accepted
time: 24ms
memory: 68744kb

input:

364465 5024701
261848032016302343703293568526235978590999513012625985721633968878034988591618605897774636291757
48911156939662778773656980542035410315871241400791196445203037239152146659698076357550328144321
29875891447314608371862077620212472448370811430738450112086482091852495958048092954883494543...

output:

? 364465
? 5024701
? 1149266098
? 2606100897
? 2001824077
! 1032717264748685811871047709887698

result:

ok Correct answer

Test #16:

score: 100
Accepted
time: 24ms
memory: 68664kb

input:

8896624 4964009
49344925857578728599084044017154495660230545751120115948542349320957762745669268814792620002447
66974004249559677557183556860692723351509484396765005933786436704210807642957818151705305711839
61173368032286811884060810029658088337353335243848166983294848185448759151958938673959592256...

output:

? 8896624
? 4964009
? 1826776534
? 2858267421
? 1225234544
! 1663384142314102128782038381738106

result:

ok Correct answer

Test #17:

score: 100
Accepted
time: 33ms
memory: 68772kb

input:

9193476 3314550
25441669503112742831369105555544218094752821957856135747534989671369083247166804998449984901797
212150633585236449498309510046700243166922201079180931718279460931642149511575099936441671657109
8972814542509014042811446416886387391204200188727272882030607849803107912542900862143183296...

output:

? 9193476
? 3314550
? 925017891
? 3197287606
? 382036344
! 718032008085820516896773256071402

result:

ok Correct answer

Test #18:

score: 100
Accepted
time: 29ms
memory: 68664kb

input:

3413745 9119715
295911975286125780198242197946500854231391950251960902357124948530287011864212557787663770233873
23130786650342398821722981843975080008589076317711022843491097736654843535389562982621104958131
7872122605218485169374539049981734500379339320424776595276728188247580137587035822592485680...

output:

? 3413745
? 9119715
? 268809678
? 3195490659
? 575404797
! 1251393044363340730693763786696884

result:

ok Correct answer

Test #19:

score: 100
Accepted
time: 27ms
memory: 68872kb

input:

4954534 9518638
81345195388144370192889742505302569835158531983788277465392811341018465276700125091559093346217
176923848900350669778898235994333374898424868510420981492601216479930969796104267338259993186551
8401539397205750396079207789044497278242438330822169272375596692151562349884358619050438628...

output:

? 4954534
? 9518638
? 55631809
? 1461657782
? 2411430238
! 1093113700184832761230415081008928

result:

ok Correct answer

Test #20:

score: 100
Accepted
time: 46ms
memory: 68704kb

input:

10 38257
192279309409462992645482090330404758368400469722499925076043266903464961794187094077107243967491
495210892832251231558827195935530998952039294078854705493131288513307539319601521094202316073111
120463673896341537073553221104929011777066175133121147294891243409816753920502139260728238335439
...

output:

? 10
? 38257
? 76504
? 1359187281
? 2864842342
! 1541118696270413738155780213019462

result:

ok Correct answer

Test #21:

score: 100
Accepted
time: 34ms
memory: 68756kb

input:

20 38267
274848544065337166381629952590164863776020394941410553373502453263042134278227621768923600557617
365782303307313856260215675116668580740950579521207503628128287627884835372501327959321222964801
15568314728517297493159918818735809952063992877838577006891299284523629209659530821674923064231
3...

output:

? 20
? 38267
? 76514
? 1359187291
? 2864842352
! 1554879545577174315177844805009670

result:

ok Correct answer

Test #22:

score: 100
Accepted
time: 37ms
memory: 68676kb

input:

38263 16
638893420971968567714171958248566593574141795092575369035153932039481282932596978554438710827827
517675015158169049881082823949129738803208988997384835064971800424824907750727512128692480493427
38867801059811515079092494174379312243167374915066631783903406458296475635658147920980544195491
4...

output:

? 38263
? 16
? 76510
? 2864842348
? 1359187287
! 1794162745260704119350320120653978

result:

ok Correct answer

Test #23:

score: 100
Accepted
time: 28ms
memory: 68716kb

input:

38259 12
378526676216666437969739656283889731375320744202713378260869712667543092115442765536443111569821
49027199494605648092727041204982535791439757766537612126407027382641109407147449789283929312613
63570325853012576028532633791887549938735886616793901466311517121869474251454965432688565885997
44...

output:

? 38259
? 12
? 76506
? 2864842344
? 1359187283
! 1669533601773935074828794438213658

result:

ok Correct answer

Test #24:

score: 100
Accepted
time: 33ms
memory: 68720kb

input:

8 318
271152087704853858846849144773423085565311346795675002902335520211991422443533270376970737358031
88911421829646188831162968471176027323173195298973895673321672917603039027016085438279065308499
105555009237263347996566548201305964855478707507282768702605747890245323136116634962708904134579
1933...

output:

? 8
? 318
? 960037955
? 3045460686
? 1774278648
! 1468220116541370919301861964467150

result:

ok Correct answer

Test #25:

score: 100
Accepted
time: 22ms
memory: 68672kb

input:

106 318
472273252837127598865745185193648976363729436108095325202899796972098454564337638297812781298607
88911421829646188831162968471176027323173195298973895673321672917603039027016085438279065308499
179079360880345620395329902871317213735131003276106628733690043013415917126582440994993289622703
32...

output:

? 106
? 318
? 410849380
? 1864689790
? 2469532614
! 1608613550805848999151899070898970

result:

ok Correct answer

Test #26:

score: 100
Accepted
time: 32ms
memory: 68880kb

input:

24979 3
105217761025430513431805365453931892161768658166365155625511683480660830982325483784059608902227
61991716112162091571854380103197141133071202062437636592434396525428433284775254050695414158203
129928662231322266613857858848623639485096506821835854993701383392015823679399449582731799885887
45...

output:

? 24979
? 3
? 2164269721
? 6820044731
? 2513133879
! 770380669474263435058256358207610

result:

ok Correct answer

Test #27:

score: 100
Accepted
time: 35ms
memory: 68676kb

input:

13 24989
116072326573391648350685971405850847952758852966666243533248737064752385451547377024175163469267
110814673525324852455895181999378620948280803211989764144379015945742091238956585898149365965801
86448222427556989757746601516364036008909340941710878190418445531054651431950974550084760430229
1...

output:

? 13
? 24989
? 215904328
? 1627962973
? 82944485
! 1252800930402819192584881286760184

result:

ok Correct answer

Test #28:

score: 100
Accepted
time: 29ms
memory: 68756kb

input:

25032 56
35051619827809683496984892713816593081366640990648656577981959939603934645644139120869938246563
31989961580711330313570961073688694480938842252236728690063459896473551878472529523497012181207
50352341837160914773846289898015298086801119605267615304737916203996716164184752442194006324149
626...

output:

? 25032
? 56
? 2164269774
? 6820044784
? 2513133932
! 834575211571173847932295141466466

result:

ok Correct answer

Test #29:

score: 100
Accepted
time: 27ms
memory: 68644kb

input:

2 38249
157117684607032845892877392705548706209112095177144931037460321967632826056713865707750900925343
375515504304785622950364341728909902316549588298426019745425853090426117160517578305153318446911
88272464868707164382887136073577663656567239166347402239812641933863101239760745354046390266529
32...

output:

? 2
? 38249
? 76496
? 1359187273
? 2864842334
! 1914928354398294561635423212831770

result:

ok Correct answer

Test #30:

score: 100
Accepted
time: 20ms
memory: 68748kb

input:

38281 34
60701507060525875944473991955071168548239622258876954257078724143413099775400567784148228656611
96581156170419729993229883474377754142170530308830583680050302173972952392165826120362091127061
39429023093436364554766802744533471662038171112165124072451006989893009855075666139063179001483
876...

output:

? 38281
? 34
? 76528
? 2864842366
? 1359187305
! 1647241379408969688821773563972916

result:

ok Correct answer

Test #31:

score: 100
Accepted
time: 27ms
memory: 68760kb

input:

36 38283
531220185583597782087209561697443114801611385567239009426661177860906252694387880879181048707521
462763072448773161690188027137652926751513590849356954955536724771982697997711018587870652691459
69538237513572961911761131890602859226313136267539215789017701503998870384602302013528690957591
3...

output:

? 36
? 38283
? 76530
? 1359187307
? 2864842368
! 1819433475872419088053950392254952

result:

ok Correct answer

Test #32:

score: 100
Accepted
time: 23ms
memory: 68652kb

input:

9278 37
103631527944084728728282522631783027738095248439773973592717376366827828043089552442642707357159
97825519574754092153758387764912275619234891313147117467743258182476235237292351844700364719169
99194285318920144747382892447743736528591730319531279282039155481745725656210484258217023328719
238...

output:

? 9278
? 37
? 795623372
? 1843851577
? 4976202466
! 1544250155193928035685283612774576

result:

ok Correct answer

Test #33:

score: 100
Accepted
time: 38ms
memory: 68880kb

input:

25 38272
33876220933137722398617805066306079054429557197443894687577106546095785453516790992855996728591
173848151833523872713758345227801860422522074831524379978344437862337640351694944099169881018611
172799112228687271597655063619690454252224966378055479425060266533870750092340408755116636340977
3...

output:

? 25
? 38272
? 76519
? 1359187296
? 2864842357
! 560642776115648517886580996274766

result:

ok Correct answer

Test #34:

score: 100
Accepted
time: 32ms
memory: 68720kb

input:

38267 20
365782303307313856260215675116668580740950579521207503628128287627884835372501327959321222964801
274848544065337166381629952590164863776020394941410553373502453263042134278227621768923600557617
15568314728517297493159918818735809952063992877838577006891299284523629209659530821674923064231
1...

output:

? 38267
? 20
? 76514
? 2864842352
? 1359187291
! 1554879545577174315177844805009670

result:

ok Correct answer

Test #35:

score: 100
Accepted
time: 31ms
memory: 68716kb

input:

26 38273
146716926280755243213766209414299815249582193069420957430975792622741860862130746636861611223471
294610316814860508766999071771110453091568148915395268312274919466041381684767271898686649715377
106661892736450510696598560669416954986621977870868835646701424390915417385110851688384995551659
...

output:

? 26
? 38273
? 76520
? 1359187297
? 2864842358
! 1214422871542797292375276838036920

result:

ok Correct answer

Test #36:

score: 100
Accepted
time: 36ms
memory: 68692kb

input:

0 6999999999999
316381285968064180556887609669772552495876860755156403387724454976348515171689788270114177166707
161781345745967290392593866204441389550059514101993008234208174023709782609702078561102434313041
201473001324711330258515519519866320048524976456042154527593511304958720977012562685774292...

output:

? 0
? 6999999999999
? 873829209
? 2763616479
? 1629227628
! 1275138320819194755791113533468724

result:

ok Correct answer

Test #37:

score: 100
Accepted
time: 35ms
memory: 68848kb

input:

6999999999999 6999999999998
161781345745967290392593866204441389550059514101993008234208174023709782609702078561102434313041
391635792520974680678334433211878729238760547841307490251068414044235884669633174088895754864379
646360101333264790704967999235278055040215775680120706834504325621873777173179...

output:

? 6999999999999
? 6999999999998
? 1214668395
? 2989372054
? 1285616579
! 1441625738869680062175657472433700

result:

ok Correct answer

Test #38:

score: 100
Accepted
time: 43ms
memory: 68996kb

input:

1999999999998 2
18460437718696539378301972546822882768126382682612598151378735196804555316218825422899476852233
157117684607032845892877392705548706209112095177144931037460321967632826056713865707750900925343
4897094682331248305495417830442462274131107138819158774887159483761051551946036777697733235...

output:

? 1999999999998
? 2
? 1965628368
? 2957425198
? 774119282
! 1546132224419237228174910416784888

result:

ok Correct answer