QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#204028#870. HackermanZhou_JKAC ✓4ms3624kbC++2311.1kb2023-10-07 00:11:312023-10-07 00:11:31

Judging History

This is the latest submission verdict.

  • [2023-10-07 00:11:31]
  • Judged
  • Verdict: AC
  • Time: 4ms
  • Memory: 3624kb
  • [2023-10-07 00:11:31]
  • Submitted

answer

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <queue>
#include <map>
#include <vector>
#include <sstream>
using namespace std;
class BigInteger
{
public:
    // constructor
    BigInteger(int = 0);
    BigInteger(long long);
    BigInteger(const string &);
    BigInteger(const char *str)
    {
        *this = string(str);
    }

    // assignment operators
    BigInteger &operator=(int num)
    {
        return *this = BigInteger(num);
    }
    BigInteger &operator=(long long num)
    {
        return *this = BigInteger(num);
    }
    BigInteger &operator=(const string &str)
    {
        return *this = BigInteger(str);
    }
    BigInteger &operator=(const char *str)
    {
        return *this = BigInteger(str);
    }

    // relational operators
    bool operator<(const BigInteger &obj) const
    {
        return cmp(obj) < 0;
    }
    bool operator>(const BigInteger &obj) const
    {
        return cmp(obj) > 0;
    }
    bool operator<=(const BigInteger &obj) const
    {
        return cmp(obj) <= 0;
    }
    bool operator>=(const BigInteger &obj) const
    {
        return cmp(obj) >= 0;
    }
    bool operator==(const BigInteger &obj) const
    {
        return cmp(obj) == 0;
    }
    bool operator!=(const BigInteger &obj) const
    {
        return cmp(obj) != 0;
    }

    // arithmetic operators
    BigInteger operator+() const
    {
        return *this;
    }
    BigInteger operator-() const
    {
        return BigInteger(-sign_, val_);
    }
    BigInteger operator+(const BigInteger &) const;
    BigInteger operator-(const BigInteger &) const;
    BigInteger operator*(const BigInteger &) const;
    BigInteger operator/(const BigInteger &) const;
    BigInteger operator%(const BigInteger &) const;

    // compound assignment operators
    BigInteger &operator+=(const BigInteger &obj)
    {
        return *this = *this + obj;
    }
    BigInteger &operator-=(const BigInteger &obj)
    {
        return *this = *this - obj;
    }
    BigInteger &operator*=(const BigInteger &obj)
    {
        return *this = *this * obj;
    }
    BigInteger &operator/=(const BigInteger &obj)
    {
        return *this = *this / obj;
    }
    BigInteger &operator%=(const BigInteger &obj)
    {
        return *this = *this % obj;
    }

    // increment and decrement operators
    BigInteger &operator++()
    {
        return *this += 1;
    }
    BigInteger &operator--()
    {
        return *this -= 1;
    }
    BigInteger operator++(int);
    BigInteger operator--(int);

    // input and output
    friend istream &operator>>(istream &, BigInteger &);
    friend ostream &operator<<(ostream &, const BigInteger &);

protected:
    enum div_type
    {
        division,
        remainder
    };
    enum cmp_type
    {
        with_sign,
        without_sign
    };
    static const int base_ = (int)1e9;
    static const int width_ = 9;
    BigInteger(int s, const vector<int> &v) : sign_(s), val_(v) {}
    int cmp(const BigInteger &, cmp_type = with_sign) const;
    BigInteger &delZero();
    BigInteger &add(const BigInteger &);
    BigInteger &sub(const BigInteger &);
    BigInteger &mul(const BigInteger &, const BigInteger &);
    BigInteger &div(BigInteger &, BigInteger, div_type = division);

private:
    int sign_;
    vector<int> val_;
};

BigInteger::BigInteger(int num) : sign_(0)
{
    if (num < 0)
        sign_ = -1, num = -num;
    else if (num > 0)
        sign_ = 1;
    do
    {
        val_.push_back(num % base_);
        num /= base_;
    } while (num);
}

BigInteger::BigInteger(long long num) : sign_(0)
{
    if (num < 0)
        sign_ = -1, num = -num;
    else if (num > 0)
        sign_ = 1;
    do
    {
        val_.push_back(num % base_);
        num /= base_;
    } while (num);
}

BigInteger::BigInteger(const string &str)
{
    sign_ = str[0] == '-' ? -1 : 1;
    int be = str[0] == '-' ? 1 : 0, en = str.size();
    while ((en -= width_) >= be)
    {
        val_.push_back(stoi(str.substr(en, width_)));
    }
    if ((en += width_) > be)
    {
        val_.push_back(stoi(str.substr(be, en - be)));
    }
    delZero();
}

BigInteger BigInteger::operator+(const BigInteger &obj) const
{
    if (sign_ * obj.sign_ == 1)
    {
        BigInteger temp;
        return cmp(obj, without_sign) >= 0 ? (temp = *this).add(obj) : (temp = obj).add(*this);
    }
    else if (sign_ * obj.sign_ == -1)
        return *this - -obj;
    else
        return sign_ == 0 ? obj : *this;
}

BigInteger BigInteger::operator-(const BigInteger &obj) const
{
    if (sign_ * obj.sign_ == 1)
    {
        BigInteger temp;
        return cmp(obj, without_sign) >= 0 ? (temp = *this).sub(obj) : (temp = -obj).sub(*this);
    }
    else if (sign_ * obj.sign_ == -1)
        return *this + -obj;
    else
        return sign_ == 0 ? -obj : *this;
}

inline BigInteger BigInteger::operator*(const BigInteger &obj) const
{
    BigInteger temp;
    return (temp.sign_ = sign_ * obj.sign_) == 0 ? temp : temp.mul(*this, obj);
}

inline BigInteger BigInteger::operator/(const BigInteger &obj) const
{
    BigInteger temp, mod = *this;
    return cmp(obj, without_sign) < 0 || (temp.sign_ = sign_ * obj.sign_) == 0 ? temp : temp.div(mod, obj);
}

inline BigInteger BigInteger::operator%(const BigInteger &obj) const
{
    BigInteger temp, mod = *this;
    return cmp(obj, without_sign) < 0 || (temp.sign_ = sign_) == 0 ? mod : temp.div(mod, obj, remainder);
}

inline BigInteger BigInteger::operator++(int)
{
    BigInteger temp = *this;
    ++*this;
    return temp;
}

inline BigInteger BigInteger::operator--(int)
{
    BigInteger temp = *this;
    --*this;
    return temp;
}

inline istream &operator>>(istream &in, BigInteger &obj)
{
    string str;
    if (in >> str)
        obj = str;
    return in;
}

ostream &operator<<(ostream &out, const BigInteger &obj)
{
    if (obj.sign_ == -1)
        out << '-';
    out << obj.val_.back();
    for (int i = obj.val_.size() - 2; i >= 0; i--)
        out << setw(BigInteger::width_) << setfill('0') << obj.val_[i];
    return out;
}

int BigInteger::cmp(const BigInteger &obj, cmp_type typ) const
{
    if (typ == with_sign && sign_ != obj.sign_)
        return sign_ - obj.sign_;
    int sign = typ == with_sign ? sign_ : 1;
    if (val_.size() != obj.val_.size())
        return sign * (val_.size() - obj.val_.size());
    for (int i = val_.size() - 1; i >= 0; i--)
        if (val_[i] != obj.val_[i])
            return sign * (val_[i] - obj.val_[i]);
    return 0;
}

inline BigInteger &BigInteger::delZero()
{
    while ((int)val_.size() > 1 && val_.back() == 0)
        val_.pop_back();
    if (val_.empty() || val_.back() == 0)
        sign_ = 0;
    return *this;
}

BigInteger &BigInteger::add(const BigInteger &obj)
{
    int os = obj.val_.size();
    val_.push_back(0);
    for (int i = 0; i < os; i++)
    {
        long long tmp = (long long)val_[i] + obj.val_[i];
        if (tmp >= base_)
            tmp -= base_, ++val_[i + 1];
        val_[i] = tmp;
    }
    return delZero();
}

BigInteger &BigInteger::sub(const BigInteger &obj)
{
    int pos = obj.val_.size();
    for (int i = 0; i < pos; i++)
    {
        long long tmp = (long long)val_[i] - obj.val_[i];
        if (tmp < 0)
            tmp += base_, --val_[i + 1];
        val_[i] = tmp;
    }
    while (val_[pos] < 0)
        val_[pos] += base_, --val_[++pos];
    return delZero();
}

BigInteger &BigInteger::mul(const BigInteger &a, const BigInteger &b)
{
    int as = a.val_.size(), bs = b.val_.size();
    val_.resize(as + bs);
    for (int i = 0; i < as; i++)
        for (int j = 0; j < bs; j++)
        {
            int x = i + j;
            long long tmp = val_[x] + (long long)a.val_[i] * b.val_[j];
            val_[x + 1] += tmp / base_;
            tmp %= base_;
            val_[x] = tmp;
        }
    return delZero();
}

BigInteger &BigInteger::div(BigInteger &a, BigInteger b, div_type typ)
{
    int move = a.val_.size() - b.val_.size();
    val_.resize(move + 1);
    b.val_.insert(b.val_.begin(), move, 0);
    for (int i = move; i >= 0; i--)
    {
        int left = 0, right = base_;
        while (left + 1 < right)
        {
            int mid = (left + right) >> 1;
            if (a.cmp(b * BigInteger(mid), without_sign) >= 0)
                left = mid;
            else
                right = mid;
        }
        val_[i] = left;
        a.sub(b * BigInteger(left));
        b.val_.erase(b.val_.begin());
    }
    return typ == division ? delZero() : a;
}
BigInteger gcd(BigInteger a,BigInteger b)
{
    return b==0?a:gcd(b,a%b);
}
#include<cassert>
const int C[3]={38247,62231,67876};
const long long INF=7000000000000; 
long long exgcd(long long a,long long b,long long &x,long long &y)
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }
    long long d=exgcd(b,a%b,x,y);
    long long tmp=x;
    x=y,y=tmp-a/b*y;
    return d;
}
long long CRT(const vector<int> &a,const vector<int> &r)
{
    assert(a.size()==r.size());
    int k=a.size();
    long long n=1,ans=0;
    for(int i=0;i<k;i++)
        n*=r[i];
    for(int i=0;i<k;i++)
    {
        long long m=n/r[i],b,y;
        exgcd(m,r[i],b,y);
        ans=(ans+(__int128)a[i]*m%n*b%n)%n;
    }
    return (ans%n+n)%n;
}
BigInteger query(long long k)
{
    cout<<"? "<<k<<endl;
    BigInteger res;
    cin>>res;
    return res;
}
bool check(long long u,int op,long long k)
{
    for(int i=0;i<3;i++)
        if(i==op)
        {
            if(k%C[i]!=u%C[i]) return false;
        }
        else if(k%C[i]==u%C[i]) return false;
    return true;
}
long long findk(long long u,long long op)
{
    long long k=u%C[op];
    while(k<INF&&!check(u,op,k)) k+=C[op];
    if(k<INF) return k;
    return -1;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    long long u,v;
    cin>>u>>v;
    BigInteger nu=query(u),nv=query(v); 
    BigInteger a[3]={0,0,0},b[3]={0,0,0};
    for(int op=0;op<=1;op++)
        if(u%C[op]==v%C[op]) a[op]=b[op]=gcd(nu,query(findk(u,op)));
    if(a[0]==0&&b[1]==0)
    {
        long long k=CRT({(int)(u%C[0]),(int)(v%C[1])},{C[0],C[1]});
        while(k%C[2]==u%C[2]||k%C[2]==v%C[2]||k%C[1]==u%C[1]||k%C[0]==v%C[0]) k+=(long long)C[0]*C[1];
        BigInteger nk=query(k);
        a[0]=gcd(nu,nk),b[1]=gcd(nv,nk);
    }
    if(a[1]==0&&b[0]==0)
    {
        long long k=CRT({(int)(u%C[1]),(int)(v%C[0])},{C[1],C[0]});
        while(k%C[2]==u%C[2]||k%C[2]==v%C[2]||k%C[0]==u%C[0]||k%C[1]==v%C[1]) k+=(long long)C[0]*C[1];
        BigInteger nk1=query(k);
        a[1]=gcd(nu,nk1),b[0]=gcd(nv,nk1);
    }
    for(int op=0;op<=1;op++)
    {
        if(a[op]==0) a[op]=gcd(nu,query(findk(u,op)));
        if(b[op]==0) b[op]=gcd(nv,query(findk(v,op)));
    }
    a[2]=nu/a[0]/a[1],b[2]=nv/b[0]/b[1];
    BigInteger res=a[0]+a[1]+a[2]+b[0]+b[1]+b[2];
    cout<<"! "<<res<<endl;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 3548kb

input:

10 20
192279309409462992645482090330404758368400469722499925076043266903464961794187094077107243967491
274848544065337166381629952590164863776020394941410553373502453263042134278227621768923600557617
506096352633800802021638751293707660624503041064291938392086928726801805924681599525227548282533
185...

output:

? 10
? 20
? 1950444022
? 429705065
! 1188670725123074098790368447122696

result:

ok Correct answer

Test #2:

score: 100
Accepted
time: 0ms
memory: 3508kb

input:

37 46
97825519574754092153758387764912275619234891313147117467743258182476235237292351844700364719169
54303479370678087384920399234466253444862272872172834147853150374135382664698264673080288884093
50233678594067149512057752145622885563364124208844922426023126492406191765427653393764870997607
163166...

output:

? 37
? 46
? 803340025
? 1576809115
! 886280847479253535234185813090550

result:

ok Correct answer

Test #3:

score: 100
Accepted
time: 2ms
memory: 3504kb

input:

44 8
139998480092642783417587715247058481747320544406167717972219233927730332587277433697128761470667
271152087704853858846849144773423085565311346795675002902335520211991422443533270376970737358031
58288433170657941476491574714892846730728452692307174479834123474745157615100697308848769680757
26473...

output:

? 44
? 8
? 1546938206
? 833210903
! 1381886467818751218186881323029526

result:

ok Correct answer

Test #4:

score: 100
Accepted
time: 3ms
memory: 3488kb

input:

82 68
188554949935264064678776197510968364875496054781466439374107711197781451374401747633705271089439
29581658567305216205082048469677895960082426925692604115399506310299669924186163606457155314301
75366448259556931974867632655700324034038750328933058158780711781659402833769015529256514177743
77134...

output:

? 82
? 68
? 601587145
? 1778562062
! 1196634362150800601617401838757468

result:

ok Correct answer

Test #5:

score: 100
Accepted
time: 3ms
memory: 3516kb

input:

6996 5792
67390022391769391147714174495294677922764805779855130049980027749475287578218791727016463145831
190199098475228480278266091225461209267710398512722346092004924897055917999060793536265245866759
35471551009262696428028264471582880821261733714596282940127909262057696267458178347773969864937
3...

output:

? 6996
? 5792
? 1753364217
? 626797628
! 1573877234916808262400484435398174

result:

ok Correct answer

Test #6:

score: 100
Accepted
time: 3ms
memory: 3544kb

input:

3291 6445
54077827831440054267656259085398546500693356922505492053613106897329930710120182867932080538157
98201039695845250970300371144288835197672318177269114670062390258285188625955203446462917390277
94264603146478479313817557733724136936894074455322016030431950005524622905350104714574451011041
28...

output:

? 3291
? 6445
? 139528347
? 2240630446
! 823431540819423718040224182607950

result:

ok Correct answer

Test #7:

score: 100
Accepted
time: 0ms
memory: 3584kb

input:

6536 5601
273599690267473575441266779803329986773862552397745534605008980423728022985536076633761206223031
156553040057872461907988875539888438079419984936293448076135238819105759558185107051162266052811
408937789777463127575758959318495732982811444726282048089465320013099215363881955262164756961933...

output:

? 6536
? 5601
? 904968803
? 1475192391
! 992834514869972328760460805894386

result:

ok Correct answer

Test #8:

score: 100
Accepted
time: 3ms
memory: 3488kb

input:

3052 4062
59574401894516890937667534231902387085142553055840275586807209737178755702430565544589840466487
296512258026557361923772900048359250214321615908774409860481069059866462678653682063649352703999
269766965952195936464698525921920577562065095483209526505134385054947953901742103127363276030293
...

output:

? 3052
? 4062
? 1822625590
? 557530581
! 1133386155345044938400896772510646

result:

ok Correct answer

Test #9:

score: 100
Accepted
time: 2ms
memory: 3584kb

input:

2991535 6681913
102329449590046183323344211216588078072166766840184965814381413975903255392300460303709193660829
330348874670800743159006181681366540512786384932812621232039970043718708269944554728671291327553
192869545848754964297572235338141055512499059658977717652845820915950426710553587100724640...

output:

? 2991535
? 6681913
? 29458459
? 2360364046
! 1453060498084516811315877375353214

result:

ok Correct answer

Test #10:

score: 100
Accepted
time: 3ms
memory: 3624kb

input:

9726238 6877918
589387736187305335574520273294597698164140932458000553468087261251075313297441776897965004482847
18779897395624462249194864702459285620828509776318474004688900021001021133252452155403252253129
2329893179368959780696531229266678092158831328766224868902064887997878634193380091197263024...

output:

? 9726238
? 6877918
? 1732294624
? 664458589
! 1206601397235349945074775565671544

result:

ok Correct answer

Test #11:

score: 100
Accepted
time: 3ms
memory: 3580kb

input:

7959578 4047401
95053938326737316266379445586202057910211242713589662088704085467691737640008981600797306083983
49795741366721729385373098164984583424703870719972940250603216863378178756906319636085914616897
32924643564081539466779148165231427293748641617130899248797325010917896674934603461680184610...

output:

? 7959578
? 4047401
? 1869670550
? 522485486
! 925097705087720494776837821836552

result:

ok Correct answer

Test #12:

score: 100
Accepted
time: 3ms
memory: 3532kb

input:

1256557 4455761
238681085596282475937506347840070769465263961322040790391335315083915661919731893116613831535629
78529459861840340884641526948023676229894459303149924455130394075003661177738785095605838942897
1114179117878889050739363916526253527390996019657573045518015885845003593765177120199828104...

output:

? 1256557
? 4455761
? 1240612345
? 1145249030
! 1356950779430279454530942638873694

result:

ok Correct answer

Test #13:

score: 100
Accepted
time: 2ms
memory: 3548kb

input:

5067300 4926563
228859205217244636912852630567243230052813454757650406883317445468737770247115670640960190511363
201484808844400742672954269627698861286759841465305062699604225148024203464672160265635695056467
260569742355201127452102632761145568114392510919131268993061067717083720784625886761004366...

output:

? 5067300
? 4926563
? 776279808
? 1613863112
! 990181739222037127397475513887002

result:

ok Correct answer

Test #14:

score: 100
Accepted
time: 2ms
memory: 3492kb

input:

3555743 7944318
82285827099855956956472351004449798422948581018031029475195444150521638632593622798977048932111
55724890135122649605027180487108321656326297217535846319578741826448763727493026873984774006863
18802799553673785322826233295081802977374391229712601635051363085629180243093232927609224062...

output:

? 3555743
? 7944318
? 1121630294
? 1270018824
! 868402917169588784171188548644790

result:

ok Correct answer

Test #15:

score: 100
Accepted
time: 4ms
memory: 3500kb

input:

364465 5024701
261848032016302343703293568526235978590999513012625985721633968878034988591618605897774636291757
48911156939662778773656980542035410315871241400791196445203037239152146659698076357550328144321
29875891447314608371862077620212472448370811430738450112086482091852495958048092954883494543...

output:

? 364465
? 5024701
? 1149266098
? 1236272125
! 1032717264748685811871047709887698

result:

ok Correct answer

Test #16:

score: 100
Accepted
time: 3ms
memory: 3548kb

input:

8896624 4964009
49344925857578728599084044017154495660230545751120115948542349320957762745669268814792620002447
66974004249559677557183556860692723351509484396765005933786436704210807642957818151705305711839
61173368032286811884060810029658088337353335243848166983294848185448759151958938673959592256...

output:

? 8896624
? 4964009
? 1826776534
? 567233156
! 1663384142314102128782038381738106

result:

ok Correct answer

Test #17:

score: 100
Accepted
time: 3ms
memory: 3576kb

input:

9193476 3314550
25441669503112742831369105555544218094752821957856135747534989671369083247166804998449984901797
212150633585236449498309510046700243166922201079180931718279460931642149511575099936441671657109
8972814542509014042811446416886387391204200188727272882030607849803107912542900862143183296...

output:

? 9193476
? 3314550
? 925017891
? 1467639192
! 718032008085820516896773256071402

result:

ok Correct answer

Test #18:

score: 100
Accepted
time: 3ms
memory: 3572kb

input:

3413745 9119715
295911975286125780198242197946500854231391950251960902357124948530287011864212557787663770233873
23130786650342398821722981843975080008589076317711022843491097736654843535389562982621104958131
7872122605218485169374539049981734500379339320424776595276728188247580137587035822592485680...

output:

? 3413745
? 9119715
? 268809678
? 2123872839
! 1251393044363340730693763786696884

result:

ok Correct answer

Test #19:

score: 100
Accepted
time: 2ms
memory: 3488kb

input:

4954534 9518638
81345195388144370192889742505302569835158531983788277465392811341018465276700125091559093346217
176923848900350669778898235994333374898424868510420981492601216479930969796104267338259993186551
8401539397205750396079207789044497278242438330822169272375596692151562349884358619050438628...

output:

? 4954534
? 9518638
? 55631809
? 2338990420
! 1093113700184832761230415081008928

result:

ok Correct answer

Test #20:

score: 100
Accepted
time: 2ms
memory: 3540kb

input:

10 38257
192279309409462992645482090330404758368400469722499925076043266903464961794187094077107243967491
495210892832251231558827195935530998952039294078854705493131288513307539319601521094202316073111
495210892832251231558827195935530998952039294078854705493131288513307539319601521094202316073111
...

output:

? 10
? 38257
? 38257
? 62241
? 100488
! 1541118696270413738155780213019462

result:

ok Correct answer

Test #21:

score: 100
Accepted
time: 2ms
memory: 3620kb

input:

20 38267
274848544065337166381629952590164863776020394941410553373502453263042134278227621768923600557617
365782303307313856260215675116668580740950579521207503628128287627884835372501327959321222964801
365782303307313856260215675116668580740950579521207503628128287627884835372501327959321222964801
...

output:

? 20
? 38267
? 38267
? 62251
? 100498
! 1554879545577174315177844805009670

result:

ok Correct answer

Test #22:

score: 100
Accepted
time: 2ms
memory: 3512kb

input:

38263 16
638893420971968567714171958248566593574141795092575369035153932039481282932596978554438710827827
517675015158169049881082823949129738803208988997384835064971800424824907750727512128692480493427
517675015158169049881082823949129738803208988997384835064971800424824907750727512128692480493427
...

output:

? 38263
? 16
? 16
? 100494
? 62247
! 1794162745260704119350320120653978

result:

ok Correct answer

Test #23:

score: 100
Accepted
time: 2ms
memory: 3516kb

input:

38259 12
378526676216666437969739656283889731375320744202713378260869712667543092115442765536443111569821
49027199494605648092727041204982535791439757766537612126407027382641109407147449789283929312613
49027199494605648092727041204982535791439757766537612126407027382641109407147449789283929312613
10...

output:

? 38259
? 12
? 12
? 100490
? 62243
! 1669533601773935074828794438213658

result:

ok Correct answer

Test #24:

score: 100
Accepted
time: 3ms
memory: 3608kb

input:

8 318
271152087704853858846849144773423085565311346795675002902335520211991422443533270376970737358031
88911421829646188831162968471176027323173195298973895673321672917603039027016085438279065308499
105555009237263347996566548201305964855478707507282768702605747890245323136116634962708904134579
1227...

output:

? 8
? 318
? 960037955
? 1420111428
! 1468220116541370919301861964467150

result:

ok Correct answer

Test #25:

score: 100
Accepted
time: 3ms
memory: 3616kb

input:

106 318
472273252837127598865745185193648976363729436108095325202899796972098454564337638297812781298607
88911421829646188831162968471176027323173195298973895673321672917603039027016085438279065308499
179079360880345620395329902871317213735131003276106628733690043013415917126582440994993289622703
66...

output:

? 106
? 318
? 410849380
? 1969300101
! 1608613550805848999151899070898970

result:

ok Correct answer

Test #26:

score: 100
Accepted
time: 1ms
memory: 3508kb

input:

24979 3
105217761025430513431805365453931892161768658166365155625511683480660830982325483784059608902227
61991716112162091571854380103197141133071202062437636592434396525428433284775254050695414158203
129928662231322266613857858848623639485096506821835854993701383392015823679399449582731799885887
28...

output:

? 24979
? 3
? 2164269721
? 215904318
! 770380669474263435058256358207610

result:

ok Correct answer

Test #27:

score: 100
Accepted
time: 3ms
memory: 3616kb

input:

13 24989
116072326573391648350685971405850847952758852966666243533248737064752385451547377024175163469267
110814673525324852455895181999378620948280803211989764144379015945742091238956585898149365965801
86448222427556989757746601516364036008909340941710878190418445531054651431950974550084760430229
1...

output:

? 13
? 24989
? 215904328
? 2164269731
! 1252800930402819192584881286760184

result:

ok Correct answer

Test #28:

score: 100
Accepted
time: 3ms
memory: 3512kb

input:

25032 56
35051619827809683496984892713816593081366640990648656577981959939603934645644139120869938246563
31989961580711330313570961073688694480938842252236728690063459896473551878472529523497012181207
50352341837160914773846289898015298086801119605267615304737916203996716164184752442194006324149
168...

output:

? 25032
? 56
? 2164269774
? 215904371
! 834575211571173847932295141466466

result:

ok Correct answer

Test #29:

score: 100
Accepted
time: 2ms
memory: 3608kb

input:

2 38249
157117684607032845892877392705548706209112095177144931037460321967632826056713865707750900925343
375515504304785622950364341728909902316549588298426019745425853090426117160517578305153318446911
375515504304785622950364341728909902316549588298426019745425853090426117160517578305153318446911
4...

output:

? 2
? 38249
? 38249
? 62233
? 100480
! 1914928354398294561635423212831770

result:

ok Correct answer

Test #30:

score: 100
Accepted
time: 2ms
memory: 3540kb

input:

38281 34
60701507060525875944473991955071168548239622258876954257078724143413099775400567784148228656611
96581156170419729993229883474377754142170530308830583680050302173972952392165826120362091127061
96581156170419729993229883474377754142170530308830583680050302173972952392165826120362091127061
116...

output:

? 38281
? 34
? 34
? 100512
? 62265
! 1647241379408969688821773563972916

result:

ok Correct answer

Test #31:

score: 100
Accepted
time: 0ms
memory: 3508kb

input:

36 38283
531220185583597782087209561697443114801611385567239009426661177860906252694387880879181048707521
462763072448773161690188027137652926751513590849356954955536724771982697997711018587870652691459
462763072448773161690188027137652926751513590849356954955536724771982697997711018587870652691459
...

output:

? 36
? 38283
? 38283
? 62267
? 100514
! 1819433475872419088053950392254952

result:

ok Correct answer

Test #32:

score: 100
Accepted
time: 3ms
memory: 3580kb

input:

9278 37
103631527944084728728282522631783027738095248439773973592717376366827828043089552442642707357159
97825519574754092153758387764912275619234891313147117467743258182476235237292351844700364719169
99194285318920144747382892447743736528591730319531279282039155481745725656210484258217023328719
195...

output:

? 9278
? 37
? 795623372
? 1584535000
! 1544250155193928035685283612774576

result:

ok Correct answer

Test #33:

score: 100
Accepted
time: 2ms
memory: 3500kb

input:

25 38272
33876220933137722398617805066306079054429557197443894687577106546095785453516790992855996728591
173848151833523872713758345227801860422522074831524379978344437862337640351694944099169881018611
173848151833523872713758345227801860422522074831524379978344437862337640351694944099169881018611
7...

output:

? 25
? 38272
? 38272
? 62256
? 100503
! 560642776115648517886580996274766

result:

ok Correct answer

Test #34:

score: 100
Accepted
time: 2ms
memory: 3584kb

input:

38267 20
365782303307313856260215675116668580740950579521207503628128287627884835372501327959321222964801
274848544065337166381629952590164863776020394941410553373502453263042134278227621768923600557617
274848544065337166381629952590164863776020394941410553373502453263042134278227621768923600557617
...

output:

? 38267
? 20
? 20
? 100498
? 62251
! 1554879545577174315177844805009670

result:

ok Correct answer

Test #35:

score: 100
Accepted
time: 2ms
memory: 3548kb

input:

26 38273
146716926280755243213766209414299815249582193069420957430975792622741860862130746636861611223471
294610316814860508766999071771110453091568148915395268312274919466041381684767271898686649715377
294610316814860508766999071771110453091568148915395268312274919466041381684767271898686649715377
...

output:

? 26
? 38273
? 38273
? 62257
? 100504
! 1214422871542797292375276838036920

result:

ok Correct answer

Test #36:

score: 100
Accepted
time: 0ms
memory: 3488kb

input:

0 6999999999999
316381285968064180556887609669772552495876860755156403387724454976348515171689788270114177166707
161781345745967290392593866204441389550059514101993008234208174023709782609702078561102434313041
201473001324711330258515519519866320048524976456042154527593511304958720977012562685774292...

output:

? 0
? 6999999999999
? 873829209
? 1487943210
! 1275138320819194755791113533468724

result:

ok Correct answer

Test #37:

score: 100
Accepted
time: 2ms
memory: 3544kb

input:

6999999999999 6999999999998
161781345745967290392593866204441389550059514101993008234208174023709782609702078561102434313041
391635792520974680678334433211878729238760547841307490251068414044235884669633174088895754864379
646360101333264790704967999235278055040215775680120706834504325621873777173179...

output:

? 6999999999999
? 6999999999998
? 1214668395
? 1128727385
! 1441625738869680062175657472433700

result:

ok Correct answer

Test #38:

score: 100
Accepted
time: 3ms
memory: 3532kb

input:

1999999999998 2
18460437718696539378301972546822882768126382682612598151378735196804555316218825422899476852233
157117684607032845892877392705548706209112095177144931037460321967632826056713865707750900925343
4897094682331248305495417830442462274131107138819158774887159483761051551946036777697733235...

output:

? 1999999999998
? 2
? 1965628368
? 1089312809
! 1546132224419237228174910416784888

result:

ok Correct answer