QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#32536#870. HackermanAutumnKiteAC ✓4ms3580kbC++178.5kb2022-05-21 10:06:472023-01-15 18:28:04

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:04]
  • Judged
  • Verdict: AC
  • Time: 4ms
  • Memory: 3580kb
  • [2022-05-21 10:06:47]
  • Submitted

answer

#include <bits/stdc++.h>

// bigint made by dengyaotriangle, modified by AutumnKite

#define __builtin_ia32_adc(x, y, flag) \
  __asm__(                             \
      "addb   %3, %0\n\t"              \
      "adcq   %2, %1\n\t"              \
      "setc   %0"                      \
      : "+r"(flag), "+r"(x)            \
      : "r"(y), "i"(-1)                \
      : "cc")

class bigint {
  using u64 = uint64_t;
  using u128 = __uint128_t;

  typedef std::size_t size_type;

  std::vector<u64> z;

public:
  bigint() {}

  bigint(u64 x) : z(x ? std::vector<u64>(1, x) : std::vector<u64>()) {}

  bigint(const std::string &s) {
    size_type pos = s.length();
    int cnt = 0;
    u64 val = 0;
    while (pos) {
      pos--;
      if (cnt == 64) {
        z.push_back(val);
        val = 0;
        cnt = 0;
      }
      val |= (u64)(s[pos] == '1') << cnt;
      ++cnt;
    }
    if (cnt && val) {
      z.push_back(val);
    }
  }

  explicit operator std::string() const {
    if (z.empty()) {
      return "0";
    }
    bool t = 0;
    std::string ret;
    for (int i = 63; i >= 0; --i) {
      t |= (z.back() >> i) & 1;
      if (t) {
        ret += '0' | ((z.back() >> i) & 1);
      }
    }
    for (size_type i = z.size() - 1; i--; ) {
      for (int j = 63; j >= 0; --j) {
        ret += '0' | ((z[i] >> j) & 1);
      }
    }
    return ret;
  }

  explicit operator bool() const {
    return !z.empty();
  }

  explicit operator u64() const {
    return z.empty() ? 0 : z[0];
  }

  size_type digit() const {
    if (z.empty()) {
      return 0;
    }
    return (z.size() << 6) - __builtin_clzll(z.back());
  }

  bool operator==(const bigint &rhs) const {
    return z == rhs.z;
  }

  bool operator!=(const bigint &rhs) const {
    return z != rhs.z;
  }

  bool operator<(const bigint &rhs) const {
    if (z.size() != rhs.z.size()) {
      return z.size() < rhs.z.size();
    }
    for (size_type i = z.size(); i--; ) {
      if (z[i] != rhs.z[i]) {
        return z[i] < rhs.z[i];
      }
    }
    return 0;
  }

  bool operator>(const bigint &rhs) const {
    return rhs < *this;
  }

  bool operator<=(const bigint &rhs) const {
    return !(rhs < *this);
  }

  bool operator>=(const bigint &rhs) const {
    return !(*this < rhs);
  }

  bigint &operator<<=(size_type n) {
    if (z.empty()) {
      return *this;
    }
    int w = n & 63;
    size_type k = n >> 6;
    size_type i = z.size();
    bool flag = false;
    if (w && (z.back() >> (64 - w))) {
      z.push_back(0);
      flag = true;
    }
    z.resize(z.size() + k);
    while (i--) {
      if (flag) {
        z[i + k + 1] |= z[i] >> (64 - w);
      }
      z[i + k] = z[i] << w;
      flag |= bool(w);
    }
    for (size_type i = 0; i < k; ++i) {
      z[i] = 0;
    }
    return *this;
  }

  bigint &operator>>=(size_type n) {
    int w = n & 63;
    size_type k = n >> 6, i = 0;
    for (; i + k < z.size(); ++i) {
      if (w && i) {
        z[i - 1] |= z[i + k] << (64 - w);
      }
      z[i] = z[i + k] >> w;
    }
    while (z.size() > i) {
      z.pop_back();
    }
    while (!z.empty() && z.back() == 0) {
      z.pop_back();
    }
    return *this;
  }

  bigint operator<<(size_type n) const {
    return bigint(*this) <<= n;
  }

  bigint operator>>(size_type n) const {
    return bigint(*this) >>= n;
  }

  bigint &operator+=(const bigint &rhs) {
    if (z.size() < rhs.z.size()) {
      z.resize(rhs.z.size());
    }
    bool carry = 0;
    for (size_type i = 0; i < z.size(); i++) {
      u64 rg = 0;
      if (i < rhs.z.size()) {
        rg = rhs.z[i];
      }
      __builtin_ia32_adc(z[i], rg, carry);
    }
    if (carry) {
      z.push_back(1);
    }
    return *this;
  }

  bigint &operator-=(const bigint &a) {
    bool carry = 1;
    for (size_type i = 0; i < z.size(); ++i) {
      u64 rg = -1;
      if (i < a.z.size()) {
        rg = ~a.z[i];
      }
      __builtin_ia32_adc(z[i], rg, carry);
    }
    while (!z.empty() && z.back() == 0) {
      z.pop_back();
    }
    return *this;
  }

  bigint &operator++() {
    return *this += bigint(1);
  }

  bigint &operator--() {
    return *this -= bigint(1);
  }

  bigint operator++(int) {
    bigint tmp = *this;
    ++*this;
    return tmp;
  }

  bigint operator--(int) {
    bigint tmp = *this;
    --*this;
    return tmp;
  }

  bigint &operator*=(const bigint &rhs) {
    std::vector<u64> ret(z.size() + rhs.z.size());
    for (size_type i = 0; i < z.size(); ++i) {
      u64 carry = 0;
      bool wcarry = 0;
      size_type k = i;
      for (size_type j = 0; j < rhs.z.size(); ++j, ++k) {
        u128 r = z[i] * (u128)rhs.z[j] + carry;
        u64 cur = r;
        carry = r >> 64;
        __builtin_ia32_adc(ret[k], cur, wcarry);
      }
      while (carry || wcarry) {
        __builtin_ia32_adc(ret[k], carry, wcarry);
        carry = 0;
        ++k;
      }
    }
    while (!ret.empty() && ret.back() == 0) {
      ret.pop_back();
    }
    z = ret;
    return *this;
  }

  bigint &operator/=(const bigint &a) {
    if (a.digit() > digit()) {
      z.clear();
      return *this;
    }
    size_type k = digit() - a.digit() + 1;
    std::vector<u64> ret;
    while (k--) {
      bigint tmp = a << k;
      if (tmp <= *this) {
        *this -= tmp;
        size_type v = k >> 6;
        if (ret.size() <= v) {
          ret.resize(v + 1);
        }
        ret[v] |= (u64)(1) << (k & 63);
      }
    }
    z = ret;
    return *this;
  }

  bigint &operator%=(const bigint &a) {
    if (a.digit() > digit()) {
      return *this;
    }
    size_type k = digit() - a.digit() + 1;
    while (k--) {
      bigint tmp = a << k;
      if (tmp <= *this) {
        *this -= tmp;
      }
    }
    return *this;
  }

  bigint operator+(const bigint &rhs) const {
    return bigint(*this) += rhs;
  }

  bigint operator-(const bigint &rhs) const {
    return bigint(*this) -= rhs;
  }

  bigint operator*(const bigint &rhs) const {
    return bigint(*this) *= rhs;
  }

  bigint operator/(const bigint &rhs) const {
    return bigint(*this) /= rhs;
  }

  bigint operator%(const bigint &rhs) const {
    return bigint(*this) %= rhs;
  }
};

std::istream &operator>>(std::istream &in, bigint &a) {
  std::string s;
  in >> s;
  a = 0;
  for (char c : s) {
    a *= 10;
    a += c - '0';
  }
  return in;
}

std::ostream &operator<<(std::ostream &out, bigint a) {
  std::string s;
  while (a) {
    s += uint64_t(a % 10) + '0';
    a /= 10;
  }
  std::reverse(s.begin(), s.end());
  if (s.empty()) {
    return out << 0;
  } else {
    return out << s;
  }
}

using i64 = int64_t;

constexpr i64 cyc[3] = {38247, 62231, 67876};

i64 exgcd(const i64 &a, const i64 &b, i64 &x, i64 &y) {
  if (!b) {
    x = 1, y = 0;
    return a;
  }
  i64 g = exgcd(b, a % b, y, x);
  y -= a / b * x;
  return g;
}

i64 crt(i64 a, const i64 &p, i64 b, const i64 &q) {
  a %= p;
  b %= q;
  i64 x, y;
  assert(exgcd(p, q, x, y) == 1);
  x *= b - a;
  i64 res = p * x + a;
  res %= p * q;
  if (res < 0) {
    res += p * q;
  }
  return res;
}

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  i64 a, b;
  std::cin >> a >> b;

  std::cout << "? " << a << std::endl;
  bigint x;
  std::cin >> x;

  std::cout << "? " << b << std::endl;
  bigint y;
  std::cin >> y;

  std::vector<int> pos;
  std::vector<bigint> px(3), py(3);
  for (int i = 0; i < 3; ++i) {
    i64 p = cyc[i], q = cyc[(i + 1) % 3], r = cyc[(i + 2) % 3];
    if (a % p == b % p) {
      i64 k = a % p;
      while (k % q == a % q || k % q == b % q ||
             k % r == a % r || k % r == b % r) {
        k += p;
      }
      std::cout << "? " << k << std::endl;
      bigint t;
      std::cin >> t;
      px[i] = std::__gcd(t, x);
      py[i] = std::__gcd(t, y);
    } else {
      pos.push_back(i);
    }
  }

  for (int i = 0; i < (int)pos.size(); ++i) {
    int j = (i + 1) % pos.size();
    i64 p = cyc[pos[i]], q = cyc[pos[j]], r = cyc[pos[i] ^ pos[j] ^ 3];
    i64 k = crt(a, p, b, q);
    while (k % r == a % r || k % r == b % r) {
      k += p * q;
    }
    std::cout << "? " << k << std::endl;
    bigint t;
    std::cin >> t;
    px[pos[i]] = std::__gcd(t, x);
    py[pos[j]] = std::__gcd(t, y);
  }

  std::cout << "! " << std::accumulate(px.begin(), px.end(), bigint()) +
                       std::accumulate(py.begin(), py.end(), bigint()) << "\n";
}

詳細信息

Test #1:

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

input:

10 20
192279309409462992645482090330404758368400469722499925076043266903464961794187094077107243967491
274848544065337166381629952590164863776020394941410553373502453263042134278227621768923600557617
506096352633800802021638751293707660624503041064291938392086928726801805924681599525227548282533
576...

output:

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

result:

ok Correct answer

Test #2:

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

input:

37 46
97825519574754092153758387764912275619234891313147117467743258182476235237292351844700364719169
54303479370678087384920399234466253444862272872172834147853150374135382664698264673080288884093
50233678594067149512057752145622885563364124208844922426023126492406191765427653393764870997607
366413...

output:

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

result:

ok Correct answer

Test #3:

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

input:

44 8
139998480092642783417587715247058481747320544406167717972219233927730332587277433697128761470667
271152087704853858846849144773423085565311346795675002902335520211991422443533270376970737358031
58288433170657941476491574714892846730728452692307174479834123474745157615100697308848769680757
31089...

output:

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

result:

ok Correct answer

Test #4:

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

input:

82 68
188554949935264064678776197510968364875496054781466439374107711197781451374401747633705271089439
29581658567305216205082048469677895960082426925692604115399506310299669924186163606457155314301
75366448259556931974867632655700324034038750328933058158780711781659402833769015529256514177743
61514...

output:

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

result:

ok Correct answer

Test #5:

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

input:

6996 5792
67390022391769391147714174495294677922764805779855130049980027749475287578218791727016463145831
190199098475228480278266091225461209267710398512722346092004924897055917999060793536265245866759
35471551009262696428028264471582880821261733714596282940127909262057696267458178347773969864937
2...

output:

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

result:

ok Correct answer

Test #6:

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

input:

3291 6445
54077827831440054267656259085398546500693356922505492053613106897329930710120182867932080538157
98201039695845250970300371144288835197672318177269114670062390258285188625955203446462917390277
94264603146478479313817557733724136936894074455322016030431950005524622905350104714574451011041
22...

output:

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

result:

ok Correct answer

Test #7:

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

input:

6536 5601
273599690267473575441266779803329986773862552397745534605008980423728022985536076633761206223031
156553040057872461907988875539888438079419984936293448076135238819105759558185107051162266052811
408937789777463127575758959318495732982811444726282048089465320013099215363881955262164756961933...

output:

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

result:

ok Correct answer

Test #8:

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

input:

3052 4062
59574401894516890937667534231902387085142553055840275586807209737178755702430565544589840466487
296512258026557361923772900048359250214321615908774409860481069059866462678653682063649352703999
269766965952195936464698525921920577562065095483209526505134385054947953901742103127363276030293
...

output:

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

result:

ok Correct answer

Test #9:

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

input:

2991535 6681913
102329449590046183323344211216588078072166766840184965814381413975903255392300460303709193660829
330348874670800743159006181681366540512786384932812621232039970043718708269944554728671291327553
192869545848754964297572235338141055512499059658977717652845820915950426710553587100724640...

output:

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

result:

ok Correct answer

Test #10:

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

input:

9726238 6877918
589387736187305335574520273294597698164140932458000553468087261251075313297441776897965004482847
18779897395624462249194864702459285620828509776318474004688900021001021133252452155403252253129
2329893179368959780696531229266678092158831328766224868902064887997878634193380091197263024...

output:

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

result:

ok Correct answer

Test #11:

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

input:

7959578 4047401
95053938326737316266379445586202057910211242713589662088704085467691737640008981600797306083983
49795741366721729385373098164984583424703870719972940250603216863378178756906319636085914616897
32924643564081539466779148165231427293748641617130899248797325010917896674934603461680184610...

output:

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

result:

ok Correct answer

Test #12:

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

input:

1256557 4455761
238681085596282475937506347840070769465263961322040790391335315083915661919731893116613831535629
78529459861840340884641526948023676229894459303149924455130394075003661177738785095605838942897
1114179117878889050739363916526253527390996019657573045518015885845003593765177120199828104...

output:

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

result:

ok Correct answer

Test #13:

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

input:

5067300 4926563
228859205217244636912852630567243230052813454757650406883317445468737770247115670640960190511363
201484808844400742672954269627698861286759841465305062699604225148024203464672160265635695056467
260569742355201127452102632761145568114392510919131268993061067717083720784625886761004366...

output:

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

result:

ok Correct answer

Test #14:

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

input:

3555743 7944318
82285827099855956956472351004449798422948581018031029475195444150521638632593622798977048932111
55724890135122649605027180487108321656326297217535846319578741826448763727493026873984774006863
18802799553673785322826233295081802977374391229712601635051363085629180243093232927609224062...

output:

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

result:

ok Correct answer

Test #15:

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

input:

364465 5024701
261848032016302343703293568526235978590999513012625985721633968878034988591618605897774636291757
48911156939662778773656980542035410315871241400791196445203037239152146659698076357550328144321
29875891447314608371862077620212472448370811430738450112086482091852495958048092954883494543...

output:

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

result:

ok Correct answer

Test #16:

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

input:

8896624 4964009
49344925857578728599084044017154495660230545751120115948542349320957762745669268814792620002447
66974004249559677557183556860692723351509484396765005933786436704210807642957818151705305711839
61173368032286811884060810029658088337353335243848166983294848185448759151958938673959592256...

output:

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

result:

ok Correct answer

Test #17:

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

input:

9193476 3314550
25441669503112742831369105555544218094752821957856135747534989671369083247166804998449984901797
212150633585236449498309510046700243166922201079180931718279460931642149511575099936441671657109
8972814542509014042811446416886387391204200188727272882030607849803107912542900862143183296...

output:

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

result:

ok Correct answer

Test #18:

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

input:

3413745 9119715
295911975286125780198242197946500854231391950251960902357124948530287011864212557787663770233873
23130786650342398821722981843975080008589076317711022843491097736654843535389562982621104958131
7872122605218485169374539049981734500379339320424776595276728188247580137587035822592485680...

output:

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

result:

ok Correct answer

Test #19:

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

input:

4954534 9518638
81345195388144370192889742505302569835158531983788277465392811341018465276700125091559093346217
176923848900350669778898235994333374898424868510420981492601216479930969796104267338259993186551
8401539397205750396079207789044497278242438330822169272375596692151562349884358619050438628...

output:

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

result:

ok Correct answer

Test #20:

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

input:

10 38257
192279309409462992645482090330404758368400469722499925076043266903464961794187094077107243967491
495210892832251231558827195935530998952039294078854705493131288513307539319601521094202316073111
120463673896341537073553221104929011777066175133121147294891243409816753920502139260728238335439
...

output:

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

result:

ok Correct answer

Test #21:

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

input:

20 38267
274848544065337166381629952590164863776020394941410553373502453263042134278227621768923600557617
365782303307313856260215675116668580740950579521207503628128287627884835372501327959321222964801
15568314728517297493159918818735809952063992877838577006891299284523629209659530821674923064231
3...

output:

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

result:

ok Correct answer

Test #22:

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

input:

38263 16
638893420971968567714171958248566593574141795092575369035153932039481282932596978554438710827827
517675015158169049881082823949129738803208988997384835064971800424824907750727512128692480493427
38867801059811515079092494174379312243167374915066631783903406458296475635658147920980544195491
4...

output:

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

result:

ok Correct answer

Test #23:

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

input:

38259 12
378526676216666437969739656283889731375320744202713378260869712667543092115442765536443111569821
49027199494605648092727041204982535791439757766537612126407027382641109407147449789283929312613
63570325853012576028532633791887549938735886616793901466311517121869474251454965432688565885997
44...

output:

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

result:

ok Correct answer

Test #24:

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

input:

8 318
271152087704853858846849144773423085565311346795675002902335520211991422443533270376970737358031
88911421829646188831162968471176027323173195298973895673321672917603039027016085438279065308499
105555009237263347996566548201305964855478707507282768702605747890245323136116634962708904134579
1933...

output:

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

result:

ok Correct answer

Test #25:

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

input:

106 318
472273252837127598865745185193648976363729436108095325202899796972098454564337638297812781298607
88911421829646188831162968471176027323173195298973895673321672917603039027016085438279065308499
179079360880345620395329902871317213735131003276106628733690043013415917126582440994993289622703
32...

output:

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

result:

ok Correct answer

Test #26:

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

input:

24979 3
105217761025430513431805365453931892161768658166365155625511683480660830982325483784059608902227
61991716112162091571854380103197141133071202062437636592434396525428433284775254050695414158203
129928662231322266613857858848623639485096506821835854993701383392015823679399449582731799885887
45...

output:

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

result:

ok Correct answer

Test #27:

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

input:

13 24989
116072326573391648350685971405850847952758852966666243533248737064752385451547377024175163469267
110814673525324852455895181999378620948280803211989764144379015945742091238956585898149365965801
86448222427556989757746601516364036008909340941710878190418445531054651431950974550084760430229
1...

output:

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

result:

ok Correct answer

Test #28:

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

input:

25032 56
35051619827809683496984892713816593081366640990648656577981959939603934645644139120869938246563
31989961580711330313570961073688694480938842252236728690063459896473551878472529523497012181207
50352341837160914773846289898015298086801119605267615304737916203996716164184752442194006324149
626...

output:

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

result:

ok Correct answer

Test #29:

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

input:

2 38249
157117684607032845892877392705548706209112095177144931037460321967632826056713865707750900925343
375515504304785622950364341728909902316549588298426019745425853090426117160517578305153318446911
88272464868707164382887136073577663656567239166347402239812641933863101239760745354046390266529
32...

output:

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

result:

ok Correct answer

Test #30:

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

input:

38281 34
60701507060525875944473991955071168548239622258876954257078724143413099775400567784148228656611
96581156170419729993229883474377754142170530308830583680050302173972952392165826120362091127061
39429023093436364554766802744533471662038171112165124072451006989893009855075666139063179001483
876...

output:

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

result:

ok Correct answer

Test #31:

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

input:

36 38283
531220185583597782087209561697443114801611385567239009426661177860906252694387880879181048707521
462763072448773161690188027137652926751513590849356954955536724771982697997711018587870652691459
69538237513572961911761131890602859226313136267539215789017701503998870384602302013528690957591
3...

output:

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

result:

ok Correct answer

Test #32:

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

input:

9278 37
103631527944084728728282522631783027738095248439773973592717376366827828043089552442642707357159
97825519574754092153758387764912275619234891313147117467743258182476235237292351844700364719169
99194285318920144747382892447743736528591730319531279282039155481745725656210484258217023328719
238...

output:

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

result:

ok Correct answer

Test #33:

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

input:

25 38272
33876220933137722398617805066306079054429557197443894687577106546095785453516790992855996728591
173848151833523872713758345227801860422522074831524379978344437862337640351694944099169881018611
172799112228687271597655063619690454252224966378055479425060266533870750092340408755116636340977
3...

output:

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

result:

ok Correct answer

Test #34:

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

input:

38267 20
365782303307313856260215675116668580740950579521207503628128287627884835372501327959321222964801
274848544065337166381629952590164863776020394941410553373502453263042134278227621768923600557617
15568314728517297493159918818735809952063992877838577006891299284523629209659530821674923064231
1...

output:

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

result:

ok Correct answer

Test #35:

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

input:

26 38273
146716926280755243213766209414299815249582193069420957430975792622741860862130746636861611223471
294610316814860508766999071771110453091568148915395268312274919466041381684767271898686649715377
106661892736450510696598560669416954986621977870868835646701424390915417385110851688384995551659
...

output:

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

result:

ok Correct answer

Test #36:

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

input:

0 6999999999999
316381285968064180556887609669772552495876860755156403387724454976348515171689788270114177166707
161781345745967290392593866204441389550059514101993008234208174023709782609702078561102434313041
201473001324711330258515519519866320048524976456042154527593511304958720977012562685774292...

output:

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

result:

ok Correct answer

Test #37:

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

input:

6999999999999 6999999999998
161781345745967290392593866204441389550059514101993008234208174023709782609702078561102434313041
391635792520974680678334433211878729238760547841307490251068414044235884669633174088895754864379
646360101333264790704967999235278055040215775680120706834504325621873777173179...

output:

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

result:

ok Correct answer

Test #38:

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

input:

1999999999998 2
18460437718696539378301972546822882768126382682612598151378735196804555316218825422899476852233
157117684607032845892877392705548706209112095177144931037460321967632826056713865707750900925343
4897094682331248305495417830442462274131107138819158774887159483761051551946036777697733235...

output:

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

result:

ok Correct answer