QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#799184#5421. Factories Once MoreMitsubachiAC ✓177ms28560kbC++178.5kb2024-12-05 01:35:212024-12-05 01:35:21

Judging History

你现在查看的是最新测评结果

  • [2024-12-05 01:35:21]
  • 评测
  • 测评结果:AC
  • 用时:177ms
  • 内存:28560kb
  • [2024-12-05 01:35:21]
  • 提交

answer

// https://qoj.ac/submission/646709

// g++-13 1.cpp -std=c++17 -O2 -I .
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
using namespace __gnu_pbds;

// #include <atcoder/modint>
// using namespace atcoder;

using ll = long long;
using ld = long double;
 
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vld = vector<ld>;
using vvld = vector<vld>;
using vst = vector<string>;
using vvst = vector<vst>;
 
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define pq_big(T) priority_queue<T,vector<T>,less<T>>
#define pq_small(T) priority_queue<T,vector<T>,greater<T>>
#define all(a) a.begin(),a.end()
#define rep(i,start,end) for(ll i=start;i<(ll)(end);i++)
#define per(i,start,end) for(ll i=start;i>=(ll)(end);i--)
#define uniq(a) sort(all(a));a.erase(unique(all(a)),a.end())

random_device seed;
mt19937_64 randint(seed());

ll grr(ll mi, ll ma) { // [mi, ma)
    return mi + randint() % (ma - mi);
}

// https://qoj.ac/submission/646709

#include <assert.h>
#include <utility>

using std::pair;
using std::swap;

// T: monoid representing information of an element and an interval.
//   T()  should return the identity.
//   T::push(T *l, T *r)  should push the lazy update.
//   T::pull(const Node *l, const Node *r)  should pull two intervals.
//     The node itself contains an element: This should calculate l * self * r.
//   T::operator<(const T &t)  is used for "Cmp" functions.
template <class T> struct Splay {
  Splay *p, *l, *r;
  T t;
  Splay() : p(nullptr), l(nullptr), r(nullptr), t() {}
  Splay(const T &t_) : p(nullptr), l(nullptr), r(nullptr), t(t_) {}
  void push() {
    t.push(l ? &l->t : nullptr, r ? &r->t : nullptr);
  }
  void pull() {
    t.pull(l ? &l->t : nullptr, r ? &r->t : nullptr);
  }
  void pushRec() {
    if (p) p->pushRec();
    push();
  }
  void rotate() {
    if (p->l == this) { if (r) { r->p = p; } p->l = r; r = p; }
    else              { if (l) { l->p = p; } p->r = l; l = p; }
    Splay *pp = p->p;
    if (pp) ((pp->l == p) ? pp->l : pp->r) = this;
    p->pull(); p->p = this; p = pp;
  }
  Splay *splay() {
    pushRec();
    for (; p; rotate()) if (p->p) ((p->l == this) == (p->p->l == p)) ? p->rotate() : rotate();
    pull();
    return this;
  }
  void linkL(Splay *a) {
    assert(!l);
    l = a; if (l) l->p = this;
    pull();
  }
  void linkR(Splay *a) {
    assert(!r);
    r = a; if (r) r->p = this;
    pull();
  }
  void linkLR(Splay *a, Splay *b) {
    assert(!l); assert(!r);
    l = a; if (l) l->p = this;
    r = b; if (r) r->p = this;
    pull();
  }
  void cutL() {
    if (l) l->p = nullptr;
    l = nullptr;
    pull();
  }
  void cutR() {
    if (r) r->p = nullptr;
    r = nullptr;
    pull();
  }
  void cutLR() {
    if (l) l->p = nullptr;
    if (r) r->p = nullptr;
    l = r = nullptr;
    pull();
  }
  // Splays the leftmost node.
  Splay *leftmost() {
    Splay *a = this;
    for (; a->l; a = a->l) {}
    return a->splay();
  }
  // Splays the rightmost node.
  Splay *rightmost() {
    Splay *a = this;
    for (; a->r; a = a->r) {}
    return a->splay();
  }
  // Iterates the tree, calling f on each node.
  template <class F> void dfs(F f) {
    push();
    if (l) l->dfs(f);
    f(this);
    if (r) r->dfs(f);
  }
  // Concatenates two trees.
  friend Splay *concat(Splay *a, Splay *b) {
    if (!a) return b;
    if (!b) return a;
    a = a->rightmost();
    a->linkR(b);
    return a;
  }
  // Splays the k-th element.
  Splay *at(int k) {
    assert(0 <= k); assert(k < t.size);
    for (Splay *a = this; ; ) {
      const int sizeL = a->l ? a->l->t.size : 0;
      if (k < sizeL) {
        a = a->l;
      } else if (k == sizeL) {
        return a->splay();
      } else {
        a = a->r;
        k -= (sizeL + 1);
      }
    }
  }
  // Splits the tree by size: [0, k), [k, a->size).
  friend pair<Splay *, Splay *> splitAt(Splay *a, int k) {
    assert(0 <= k); assert(k <= (a ? a->t.size : 0));
    if (k == 0) return std::make_pair(nullptr, a);
    if (k == a->t.size) return std::make_pair(a, nullptr);
    a = a->at(k);
    Splay *l = a->l;
    a->cutL();
    return std::make_pair(l, a);
  }
  // Splits the tree by operator<: (< target), (>= target).
  // Splays the rightmost (< target) and the leftmost (>= target).
  friend pair<Splay *, Splay *> splitCmp(Splay *a, const T &target) {
    Splay *l = nullptr, *r = nullptr;
    for (; a; ) {
      a->push();
      if (a->t < target) {
        l = a;
        a = a->r;
      } else {
        r = a;
        a = a->l;
      }
    }
    if (l) {
      l->splay();
      l->cutR();
    }
    if (r) r->splay();
    return std::make_pair(l, r);
  }
  // Inserts b into the tree, using T::operator<.
  friend void insertCmp(Splay *&a, Splay *b) {
    auto s = splitCmp(a, b->t);
    b->linkLR(s.first, s.second);
    a = b;
  }
  // Inserts b's nodes into the tree one by one, using T::operator<.
  friend void meldRecCmp(Splay *&a, Splay *b) {
    if (!b) return;
    Splay *l = b->l, *r = b->r;
    b->push();
    b->cutLR();
    meldRecCmp(a, l);
    insertCmp(a, b);
    meldRecCmp(a, r);
  }
  // Meld two trees, using T::operator<.
  friend Splay *meldCmp(Splay *a, Splay *b) {
    if (!a) return b;
    if (!b) return a;
    if (a->t.size < b->t.size) swap(a, b);
    meldRecCmp(a, b);
    return a;
  }
  // Cuts out [kL, kR) of the tree and calls f.
  template <class F> friend void range(Splay *&a, int kL, int kR, F f) {
    assert(0 <= kL); assert(kL <= kR); assert(kR <= (a ? a->t.size : 0));
    if (kL == kR) { f(nullptr); return; }
    Splay *b = nullptr;
    if (kR < a->t.size) {
      b = a->at(kR);
      a = b->l;
      b->cutL();
    }
    if (0 < kL) a = a->at(kL - 1)->r;
    f(a);
    if (b) b->linkL(a->splay());
    a->splay();
  }
  // Applies T::f(args...) to [kL, kR).
  template <class F, class... Args>
  friend void ch(Splay *&a, int kL, int kR, F f, Args &&... args) {
    range(a, kL, kR, [&](Splay *b) -> void { if (b) (b->t.*f)(args...); });
  }
  // Calculates the product for [kL, kR).
  friend T get(Splay *&a, int kL, int kR) {
    T t;
    range(a, kL, kR, [&](Splay *b) -> void { if (b) t = b->t; });
    return t;
  }
};

struct Node {
  int size; // 今の木の頂点の部分木のサイズ
  int sizeL; // 今の木の頂点の部分木のサイズ, 自分より大きい値の数
  long long val; // 自分の頂点の値
  long long lazy_a; // 部分木全体に足すべき等差数列の初項
  long long lazy_b; // 部分木全体に足すべき等差数列の交差

  Node() : size(0),sizeL(0),val(0),lazy_a(0),lazy_b(0) {} // 無
  Node(long long val_) : size(1),sizeL(0),val(val_),lazy_a(0),lazy_b(0) {} // 単一頂点
  void add(long long a,long long b){
    // 自分の頂点に等差数列を反映
    val+=a+b*sizeL;
    lazy_a+=a; // 子供への遅延
    lazy_b+=b; // 子供への遅延
  }
  void push(Node *l, Node *r) {
    if(l){
      l->add(lazy_a,lazy_b);
    }
    if(r){
      r->add(lazy_a+lazy_b*(sizeL+1),lazy_b);
    }
    lazy_a=0;
    lazy_b=0;
  }
  void pull(const Node *l, const Node *r) {
    size = (l ? l->size : 0) + 1 + (r ? r->size : 0);
    sizeL = (l ? l->size : 0);
  }
  bool operator<(const Node &t) {
    return (val>t.val); // 自分の頂点の値が大きい方を先にしたい -> < が成り立つように
  }
};

int mxn = 1e5+10;

vector<Splay<Node>> nodes(mxn);

Splay<Node> *solve(int now,int pre,vector<vector<pair<int,ll>>> &g,int n,int k){
  nodes[now]=Node(0);
  auto res=&nodes[now];
  for(auto [nxt,w]:g[now]){
    if(nxt==pre)continue;
    auto sub=solve(nxt,now,g,n,k);
    ch(sub,0,sub->t.size,&Node::add,w*(k-1),-2*w);
    // sub の部分木で hoge 番目までに add(w*(k-1),-2*w) を作用
    res=meldCmp(res,sub);
    // 部分木の合体
  }
  return res;
}


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

  int n,k;cin>>n>>k;
  vector<vector<pair<int,ll>>> g(n);
  rep(i,0,n-1){
    int u,v;
    ll w;
    cin>>u>>v>>w;
    u--;v--;
    g[u].emplace_back(v,w);
    g[v].emplace_back(u,w);
  }
  auto ans=solve(0,-1,g,n,k);
  ll sum=0;
  int cnt=0;
  ans->dfs([&](Splay<Node> *a){
    if(cnt++<k)sum+=a->t.val;
  });
  cout<<sum<<endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

6 3
1 2 3
2 3 2
2 4 1
1 5 2
5 6 3

output:

22

result:

ok 1 number(s): "22"

Test #2:

score: 0
Accepted
time: 2ms
memory: 8332kb

input:

4 3
1 2 2
1 3 3
1 4 4

output:

18

result:

ok 1 number(s): "18"

Test #3:

score: 0
Accepted
time: 0ms
memory: 8400kb

input:

2 2
1 2 1

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 103ms
memory: 17356kb

input:

100000 17
37253 35652 9892
56367 53643 1120
47896 49255 4547
93065 88999 1745
5251 6742 5031
49828 50972 8974
31548 46729 1032
56341 56287 4812
21896 22838 1682
82124 90557 7307
76289 76949 7028
33834 45380 6856
15499 15064 2265
10127 5251 9920
87208 93945 9487
68990 72637 6891
91640 85004 2259
4748...

output:

4915539756

result:

ok 1 number(s): "4915539756"

Test #5:

score: 0
Accepted
time: 87ms
memory: 17388kb

input:

100000 54
52645 54121 2692
53845 52739 658
88841 87795 9298
79147 80362 6720
80683 80909 7138
30882 28439 3197
85375 85227 6903
80229 77345 445
79601 78148 7956
15262 16666 8402
87894 95824 844
17024 12005 5687
63972 65707 8592
40510 45074 9135
50774 49596 7692
37825 38581 9735
18425 8926 1747
84473...

output:

42231195087

result:

ok 1 number(s): "42231195087"

Test #6:

score: 0
Accepted
time: 92ms
memory: 16996kb

input:

100000 102
16851 15608 9173
34201 33232 4258
54234 53975 3926
85209 83376 6251
7847 6527 2379
92238 90747 5818
74729 75538 1672
98398 98838 6273
53445 54006 4317
32889 33232 9974
12450 15916 1801
40600 40892 1397
81713 79934 4580
28979 30696 8260
90747 94477 5725
54584 53210 3583
53396 53535 1868
88...

output:

175914470238

result:

ok 1 number(s): "175914470238"

Test #7:

score: 0
Accepted
time: 93ms
memory: 17408kb

input:

100000 497
25231 28005 505
36245 34348 7087
59602 57941 1691
77459 74493 7828
11601 4890 9847
11168 11760 3807
97468 93452 8094
14843 13669 488
97738 96869 5615
27369 25231 3081
79596 78931 4604
47155 45416 1728
49273 49193 7851
38358 38735 4842
18025 23117 6165
32677 32970 9931
34174 35023 9709
688...

output:

4545765711714

result:

ok 1 number(s): "4545765711714"

Test #8:

score: 0
Accepted
time: 110ms
memory: 16916kb

input:

100000 1008
9180 10823 9475
54255 56689 9732
42103 43318 4094
11647 12305 5651
63247 66770 513
88023 85592 3518
65473 66850 7176
3995 6958 9978
2408 780 982
71617 71736 9828
22243 19070 9488
41041 40935 2604
2697 6337 8631
90433 86018 7306
73087 76067 9705
92594 99998 6304
70188 68983 8730
13139 132...

output:

11601533653407

result:

ok 1 number(s): "11601533653407"

Test #9:

score: 0
Accepted
time: 76ms
memory: 17632kb

input:

100000 4998
4535 1424 2772
79531 75798 6655
29016 24101 7995
82506 82511 2829
62622 55576 6770
13299 12683 7014
10087 7482 4906
54613 61198 7397
38305 37235 7840
78676 78348 906
68742 70584 5410
96124 96972 9461
84908 86633 3419
99187 98820 1644
34611 31584 1458
18895 19637 6568
38305 39973 5203
324...

output:

464391127886092

result:

ok 1 number(s): "464391127886092"

Test #10:

score: 0
Accepted
time: 99ms
memory: 17272kb

input:

100000 9995
65827 63216 3734
63002 63137 8069
19664 18828 9617
93059 93073 5416
98904 95848 3168
32077 28643 9290
85544 83781 4681
79065 75963 8553
52322 55020 5603
19063 21141 9921
17961 14354 9378
46073 48153 7631
44812 43844 24
72171 73621 177
28060 35086 186
96739 99367 1792
39346 41459 6809
254...

output:

1257975734249836

result:

ok 1 number(s): "1257975734249836"

Test #11:

score: 0
Accepted
time: 102ms
memory: 17088kb

input:

100000 20006
61719 62750 1537
44716 44507 9463
9473 13052 6509
88729 91128 7872
17510 17537 3948
31118 28068 695
84397 87761 9471
46545 52049 9288
40481 42157 9669
77649 82807 4870
25263 34334 9049
87761 87116 9621
21481 22885 9068
12531 13961 118
4102 1090 7301
73658 74721 1190
93332 93176 6754
139...

output:

3909625330770761

result:

ok 1 number(s): "3909625330770761"

Test #12:

score: 0
Accepted
time: 96ms
memory: 16764kb

input:

100000 29995
66648 66845 615
78793 82917 393
30618 30893 6890
41131 47190 2221
32237 29954 5180
10751 11344 9708
16679 24041 3164
3831 4548 6498
35913 36039 6878
68601 68877 8110
92574 90108 1134
73318 69034 7615
90627 91083 9287
36029 35913 1051
16212 16646 223
6363 8579 8028
10146 8221 7063
28900 ...

output:

4268090067787386

result:

ok 1 number(s): "4268090067787386"

Test #13:

score: 0
Accepted
time: 99ms
memory: 17104kb

input:

100000 40006
49562 51918 866
17806 19107 2846
71022 67295 6070
71022 70056 7385
94889 89640 9947
60828 58184 5033
71022 66532 1731
62336 71022 6793
16617 12279 152
39363 38384 5282
85971 71022 8362
98005 98950 3189
71022 78198 7477
90400 91683 6922
92599 94033 4625
11778 20231 1738
95212 94195 8471
...

output:

24780741739486839

result:

ok 1 number(s): "24780741739486839"

Test #14:

score: 0
Accepted
time: 88ms
memory: 17388kb

input:

100000 50009
11519 12909 6102
8376 9090 948
24653 21957 5015
78673 77914 8012
94387 86135 7704
74259 71676 3180
32316 34697 2345
5053 1437 5673
71861 72457 4201
3422 2275 3317
24653 20485 5187
24653 24621 8398
47636 48019 3626
17947 19814 6274
98755 87800 3696
4427 3574 6916
45165 45343 4296
56784 6...

output:

25351043829274168

result:

ok 1 number(s): "25351043829274168"

Test #15:

score: 0
Accepted
time: 90ms
memory: 17704kb

input:

100000 59998
26594 26562 5650
67934 67666 7744
95475 96987 9428
85081 85490 7193
89263 91549 4061
18759 12481 4975
40611 43808 8565
8290 6906 9079
33833 38872 9736
41640 43323 3864
53606 52990 5899
16499 19319 2061
15814 13300 1889
74493 80450 2797
35299 37587 4082
43676 42897 9008
90523 91839 73
38...

output:

26966451993136100

result:

ok 1 number(s): "26966451993136100"

Test #16:

score: 0
Accepted
time: 82ms
memory: 18376kb

input:

100000 70005
10361 8490 4865
83066 87336 6030
58320 58359 4626
94784 95690 6034
1123 2601 4183
65881 68588 1580
54073 53135 4584
45524 47959 6836
76817 74258 7574
22525 22678 4797
97745 98937 807
10150 9465 5254
34297 42007 4933
60941 60341 2810
24040 19465 5435
30622 31196 3132
1760 167 8819
40256 ...

output:

104641034755167014

result:

ok 1 number(s): "104641034755167014"

Test #17:

score: 0
Accepted
time: 92ms
memory: 17224kb

input:

100000 79999
22117 12828 5672
65501 64977 3295
67636 68226 818
30886 30980 9375
71032 78661 4633
52941 50190 4696
44197 48980 9195
18619 18709 7446
64987 63040 1983
38286 38513 1504
12656 18464 1474
38372 38284 6925
65882 66995 3453
42274 41350 9100
8406 6453 7166
76320 76959 1476
79315 79714 1556
7...

output:

25968154522227868

result:

ok 1 number(s): "25968154522227868"

Test #18:

score: 0
Accepted
time: 90ms
memory: 18312kb

input:

100000 90009
21392 15740 4838
10745 10469 3544
57003 54406 2863
49678 43586 3467
67781 70239 8450
47532 45410 194
24939 25863 5952
30027 31357 3950
47896 44616 3902
91118 90632 8013
41375 39235 2164
39264 32561 7567
4476 2275 8419
14714 20159 8515
11566 9728 5719
11014 10536 8388
67781 66459 5638
74...

output:

59839375269101890

result:

ok 1 number(s): "59839375269101890"

Test #19:

score: 0
Accepted
time: 98ms
memory: 17708kb

input:

100000 95010
2406 3525 5185
67257 65609 7664
52387 53009 9861
17546 15653 8894
60448 60952 2761
25320 25633 9796
96057 96520 2104
41271 41659 6773
42607 41271 8077
97542 98735 268
5549 7077 7092
73181 67888 3403
10379 11403 7455
22873 15738 8725
44656 42979 1283
62388 63279 7646
69964 65707 9391
210...

output:

24470577265870980

result:

ok 1 number(s): "24470577265870980"

Test #20:

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

input:

100000 98996
7641 8510 354
28744 30040 7127
66707 70077 7735
78713 78328 4388
12575 15440 4102
41233 40610 2349
67726 66752 8181
75700 75384 961
93655 94760 1233
16294 8191 6568
54353 57725 4711
90342 94013 1248
47394 41233 6554
59828 58429 5837
36314 41233 9928
53019 50634 9765
3848 1517 3192
58395...

output:

53466838342649132

result:

ok 1 number(s): "53466838342649132"

Test #21:

score: 0
Accepted
time: 98ms
memory: 18136kb

input:

100000 99492
39670 39654 6671
30881 30657 8093
11265 11400 8734
97584 96799 970
94844 94463 7358
11888 11219 7833
20073 26116 4213
41939 41545 4654
35512 35656 9281
94181 95605 4387
36418 39025 2894
31917 30118 9754
11160 7637 988
58865 64112 203
34643 34098 3049
23032 24245 7370
83912 87151 9663
24...

output:

46085514901930803

result:

ok 1 number(s): "46085514901930803"

Test #22:

score: 0
Accepted
time: 94ms
memory: 17428kb

input:

100000 99892
46639 50871 9287
82116 81069 96
60153 62342 65
57966 58198 4466
79426 76499 3164
65312 60339 412
99807 96826 1715
13185 11839 4073
11647 12511 5614
35068 31821 3727
79093 75387 1146
53817 55040 8198
33916 34594 9101
14277 13456 4818
61364 60496 6316
42951 43738 378
73516 74081 6701
8867...

output:

51760329631371741

result:

ok 1 number(s): "51760329631371741"

Test #23:

score: 0
Accepted
time: 83ms
memory: 18020kb

input:

100000 99957
44986 45640 2910
90982 92758 6033
78971 78388 8976
61852 61689 4423
49757 49941 8426
45251 45682 8727
53546 52754 5452
63232 73333 165
87912 92656 6118
4407 2404 5402
3407 119 4113
81578 77351 8515
47167 47940 6931
30343 30485 3401
33857 32333 5987
56262 57721 1245
36658 44071 7652
5930...

output:

130410495204372446

result:

ok 1 number(s): "130410495204372446"

Test #24:

score: 0
Accepted
time: 89ms
memory: 18232kb

input:

100000 99999
10082 9154 1246
3880 1692 254
53354 57325 4812
75463 72641 2326
50203 58561 7663
14156 13314 1096
62646 59220 6107
82660 83186 473
16969 14707 3988
16585 14586 8460
47747 41206 3108
96538 93261 6818
22308 28561 6963
24921 30386 9931
15121 15172 8291
13683 14201 6120
29796 29195 6001
806...

output:

87424565196236766

result:

ok 1 number(s): "87424565196236766"

Test #25:

score: 0
Accepted
time: 91ms
memory: 17084kb

input:

100000 10000
31462 73242 8081
2735 23184 1920
81381 76168 2596
48792 82888 4854
2067 72576 3656
78656 7981 1901
6414 17943 7268
72191 9524 3594
2105 16798 5703
69815 62446 5729
3601 60479 807
71907 59764 6777
31061 64788 6033
18466 4265 4331
16371 34680 1690
99067 34531 7911
8733 33370 7400
39904 39...

output:

1093865271742605

result:

ok 1 number(s): "1093865271742605"

Test #26:

score: 0
Accepted
time: 98ms
memory: 16952kb

input:

100000 20010
51395 85878 3735
83482 60660 3548
1370 92576 8866
83916 81421 6866
99829 58260 7251
99446 33675 8475
5446 89548 6683
75262 86069 1728
29067 70344 3180
99787 83204 7136
13754 36484 5044
95014 77748 2949
19617 8442 7497
372 61265 9806
88714 27646 1303
53849 11687 3480
4899 75029 9890
9056...

output:

3098745825030603

result:

ok 1 number(s): "3098745825030603"

Test #27:

score: 0
Accepted
time: 89ms
memory: 16884kb

input:

100000 30000
33385 14282 9623
86293 93937 7084
2729 8733 9762
32594 57151 4695
93045 31900 254
31535 42479 4538
41890 60020 8906
10539 7320 8201
69877 31242 9799
88706 11497 1033
95444 89110 371
89093 4180 3370
77642 97214 7193
9432 22562 2938
44588 23030 8318
39797 66578 122
54033 48506 7389
31581 ...

output:

4853364869251381

result:

ok 1 number(s): "4853364869251381"

Test #28:

score: 0
Accepted
time: 99ms
memory: 17536kb

input:

100000 39990
59213 45303 309
82753 34495 9402
69391 84987 646
54355 83664 4935
9169 22200 178
28621 80012 9332
72331 73505 5467
74795 62364 572
46523 33576 2539
18489 17868 9338
25848 8594 2961
51620 74291 2193
12509 34579 1699
75148 4680 6693
58425 74545 8294
56090 35780 2133
72719 90297 8188
88029...

output:

7392046918450952

result:

ok 1 number(s): "7392046918450952"

Test #29:

score: 0
Accepted
time: 85ms
memory: 17248kb

input:

100000 50004
41905 60103 1169
90128 77953 1907
73426 82310 4709
10981 73393 3976
92253 34948 1675
5464 66270 4417
95891 84704 2789
23311 32006 6900
38333 63762 4950
78878 40279 21
23427 91067 2605
38685 37096 6258
33094 28520 9614
66406 43980 8814
57287 97117 6925
70518 83555 5520
60183 81340 8978
9...

output:

22262772179288343

result:

ok 1 number(s): "22262772179288343"

Test #30:

score: 0
Accepted
time: 93ms
memory: 17860kb

input:

100000 59990
42130 25585 6622
19141 89932 5127
88368 76887 6563
23541 67372 2136
54400 22220 2902
72782 75555 8069
30118 54373 8236
81556 53920 5967
39012 25786 7645
85906 54258 5265
72242 99011 5989
17039 25635 8264
19269 78746 3215
33518 18146 4887
21787 72616 5899
87829 72645 4477
676 2975 9750
8...

output:

25849812417537701

result:

ok 1 number(s): "25849812417537701"

Test #31:

score: 0
Accepted
time: 89ms
memory: 17072kb

input:

100000 70005
59019 99742 8432
72636 26129 8100
87851 89509 5862
10431 59763 44
33664 43615 6355
95813 19407 4245
78138 5093 747
42969 30353 501
93457 63214 1679
487 89588 112
24215 36929 3516
59173 47233 5403
3508 14359 6025
7982 87257 4063
14892 24213 8219
11125 9956 5949
85440 16593 1198
81839 123...

output:

23949712954762540

result:

ok 1 number(s): "23949712954762540"

Test #32:

score: 0
Accepted
time: 91ms
memory: 17948kb

input:

100000 79990
45269 56436 9138
96120 19334 104
32661 24366 1518
6898 40947 8163
70305 70790 2357
44223 84620 1284
56747 65134 3292
99269 93027 3431
4251 82085 9250
56735 92140 8825
99180 96937 2735
16525 35563 666
22027 32433 6534
2211 86542 4168
24045 43038 884
35083 6627 9730
77394 94646 2397
76232...

output:

24315977667796687

result:

ok 1 number(s): "24315977667796687"

Test #33:

score: 0
Accepted
time: 87ms
memory: 18572kb

input:

100000 90001
93543 21520 4780
24160 40646 7211
45224 74106 4095
70963 51695 1287
10114 34867 1258
48508 65786 3561
24765 93348 5711
98097 69713 1114
90495 82081 5954
27393 43799 8097
62051 31931 3184
50115 44851 3593
70486 83686 2418
55723 56779 9954
96850 51643 4654
48701 48865 6495
87843 64382 403...

output:

64667342284599340

result:

ok 1 number(s): "64667342284599340"

Test #34:

score: 0
Accepted
time: 140ms
memory: 17456kb

input:

100000 10004
53761 70504 9556
40754 16014 9123
48943 5811 6314
44466 34279 4167
40142 44201 7776
61297 89338 9276
53325 651 6514
74280 78120 9591
78355 6311 8729
31471 76686 9995
98331 56276 5380
33421 61585 3019
68703 29190 5334
15367 40389 2525
41815 20105 8382
91412 8515 5675
10222 4148 3030
9335...

output:

12277872546429

result:

ok 1 number(s): "12277872546429"

Test #35:

score: 0
Accepted
time: 146ms
memory: 17720kb

input:

100000 19994
18049 20868 3894
59091 46504 6072
43410 7435 7331
15573 70346 7360
43041 48051 8173
99520 25593 2239
45903 36459 9670
22730 45300 6794
48781 60656 2607
85717 32561 6937
22353 68000 8733
67790 38947 1094
63523 51473 5929
87418 97070 8467
75572 7364 5388
70197 36884 3300
80995 48648 717
7...

output:

45500536942634

result:

ok 1 number(s): "45500536942634"

Test #36:

score: 0
Accepted
time: 143ms
memory: 17612kb

input:

100000 30005
70647 3878 4021
83333 36307 458
5052 43248 9333
56462 61856 1886
58099 54995 2950
62717 30263 3069
12005 61212 5993
4488 36658 9249
39703 42114 4131
95697 25020 8493
11842 89422 304
85201 21661 2295
51700 33685 2065
33474 15945 9583
80802 87796 713
23486 77997 62
95525 52467 6227
22618 ...

output:

100023088797832

result:

ok 1 number(s): "100023088797832"

Test #37:

score: 0
Accepted
time: 145ms
memory: 17712kb

input:

100000 39990
38889 73960 333
39359 69696 5668
27307 87074 8648
8 67421 1404
51446 54362 5415
98637 56320 4170
78501 58647 9276
32205 33841 3552
48380 14304 4
5841 99117 4939
84789 14515 3245
14281 61470 6651
37475 59214 6799
10097 23892 9758
22390 23583 3660
52455 56067 1449
99586 33095 7949
41851 7...

output:

177183691693398

result:

ok 1 number(s): "177183691693398"

Test #38:

score: 0
Accepted
time: 147ms
memory: 17536kb

input:

100000 50005
48261 57991 8408
69313 6876 8310
7089 36443 3786
41169 57498 2294
14622 32021 8496
16626 87593 3820
24612 20600 6129
49506 89823 3454
53348 71960 1519
70641 35492 1861
20102 81318 7807
87705 99412 4801
10535 46015 8246
41360 85364 9141
66092 92345 4494
17805 74400 8542
79183 72196 9572
...

output:

253595270466688

result:

ok 1 number(s): "253595270466688"

Test #39:

score: 0
Accepted
time: 144ms
memory: 17652kb

input:

100000 59995
98352 83604 2432
50217 44564 9015
30700 57244 5684
29976 32765 3876
28411 29267 4284
30196 51355 1882
59031 17173 767
88169 91548 1041
53184 62432 4061
67356 98230 1960
10706 12276 410
33546 29324 6433
59996 72128 7996
73105 52020 3577
16366 42436 974
20879 57576 2563
51222 34602 6491
5...

output:

347805937723168

result:

ok 1 number(s): "347805937723168"

Test #40:

score: 0
Accepted
time: 148ms
memory: 17396kb

input:

100000 70005
64679 40628 4106
70960 33215 5334
17557 44727 4346
61154 6100 1682
17290 22239 1350
9169 72554 929
7215 33959 9062
22443 87848 4633
24372 19020 1871
72329 88743 9455
67029 81915 145
24260 48459 8123
32987 92184 4870
85628 43 4463
47005 93471 2671
82838 39218 3300
56415 7484 7889
68827 5...

output:

471187300367026

result:

ok 1 number(s): "471187300367026"

Test #41:

score: 0
Accepted
time: 147ms
memory: 17388kb

input:

100000 79995
13231 26252 4255
68679 39756 1125
56088 7531 761
86830 65335 2531
14415 78843 8648
8127 96735 4905
30340 90262 8630
8358 18301 2993
89486 80376 6571
95230 17403 7330
90253 12384 9255
71369 35287 8381
93822 6134 6959
55115 97340 2145
76030 47549 4566
68446 49170 2688
57345 81866 5513
675...

output:

619412519494252

result:

ok 1 number(s): "619412519494252"

Test #42:

score: 0
Accepted
time: 149ms
memory: 17740kb

input:

100000 89994
28092 68989 2670
65776 66823 487
68478 72175 806
27747 54834 5296
11377 73361 9774
28096 9728 9563
67399 12939 7001
27703 59498 6238
61540 55214 3623
58852 41389 1954
58125 89445 2147
97289 25006 3576
37134 44398 3256
51944 38075 2160
23981 50972 3647
38734 69465 2528
29122 31697 1795
6...

output:

697703431675028

result:

ok 1 number(s): "697703431675028"

Test #43:

score: 0
Accepted
time: 90ms
memory: 19592kb

input:

100000 10005
27045 60830 5988
12707 34362 2018
91445 2294 7898
7818 54723 7177
13837 9917 5721
69980 11380 5864
16644 72835 5228
85025 59964 3078
19937 71226 5956
43471 60573 2704
31996 2958 8676
53521 93945 9051
40013 89641 2035
41498 9199 4215
33263 5135 782
14215 55222 8108
86571 9538 1655
89919 ...

output:

4863957909657110

result:

ok 1 number(s): "4863957909657110"

Test #44:

score: 0
Accepted
time: 88ms
memory: 20820kb

input:

100000 19998
83940 86462 4127
40828 61304 5830
82186 58276 9804
13293 80517 5524
42467 91683 4023
80711 36944 4850
60539 34448 4069
62883 3916 9446
69293 71730 1176
44819 84556 2965
83781 13744 9289
93752 89188 4246
18907 28967 9126
35069 5630 2326
93328 76301 3454
44826 32854 6465
17592 82518 2251
...

output:

21158782694756705

result:

ok 1 number(s): "21158782694756705"

Test #45:

score: 0
Accepted
time: 91ms
memory: 19780kb

input:

100000 30005
78672 5903 5973
4194 1399 4907
33947 3445 433
85018 33831 5825
91258 10277 3500
32838 82203 7857
3327 74575 5794
31815 15718 4098
42593 39096 70
1980 78982 4787
56091 20792 6363
29590 92936 5642
25304 5751 508
74078 53001 5576
38495 92888 5219
67675 24081 6429
20169 64712 6626
30147 556...

output:

49362609987601430

result:

ok 1 number(s): "49362609987601430"

Test #46:

score: 0
Accepted
time: 97ms
memory: 19980kb

input:

100000 39999
169 23032 1259
3707 65546 706
80759 91442 2540
30923 90912 7515
31881 88598 5162
95913 89635 4898
1646 71893 9830
33699 38712 8295
84082 58320 4775
6531 49487 4030
21014 78798 580
43044 86357 7254
13729 10803 8978
21858 38737 6350
91281 21392 1876
24394 55859 8989
94743 19407 957
31241 ...

output:

49845846755665914

result:

ok 1 number(s): "49845846755665914"

Test #47:

score: 0
Accepted
time: 89ms
memory: 20100kb

input:

100000 50009
29258 15215 7439
9463 90815 1903
69475 6028 9511
17212 5839 9820
6925 79846 2560
23120 3753 1420
51053 428 785
13842 81186 5776
41937 36488 8449
68498 71159 3799
40195 19974 2596
31121 41357 1944
19408 84491 8447
9417 71519 3150
33962 31788 8185
15615 4252 2122
70608 34613 2489
31023 67...

output:

88419031612315262

result:

ok 1 number(s): "88419031612315262"

Test #48:

score: 0
Accepted
time: 79ms
memory: 19388kb

input:

100000 60008
43447 41405 4176
80008 22616 6696
64762 38391 7361
5417 97050 4029
74086 23245 9265
78745 2891 9373
15199 58331 8090
16743 24988 3376
22866 40074 1277
59333 59861 5377
27355 59514 7977
2873 87137 3303
14220 42351 4975
51498 32256 3932
29104 1929 4305
98611 63279 343
2711 94115 4886
2913...

output:

133597463176537971

result:

ok 1 number(s): "133597463176537971"

Test #49:

score: 0
Accepted
time: 70ms
memory: 21404kb

input:

100000 70002
71628 67166 823
8233 1120 9509
20067 60958 4891
91848 69985 6471
2323 18263 8951
36617 93409 6036
96395 26025 1395
32012 36338 1479
63780 97452 4607
20228 20871 9582
40684 66203 675
10051 36762 3886
36658 67605 2005
1340 20910 1525
45212 83934 1282
77211 549 4828
48967 99562 2174
81610 ...

output:

200162856677263187

result:

ok 1 number(s): "200162856677263187"

Test #50:

score: 0
Accepted
time: 73ms
memory: 20600kb

input:

100000 80008
40505 91360 5107
7509 82113 4925
20353 58570 3337
54227 18237 2967
65829 26473 8835
75842 44031 41
71439 14026 3022
800 83423 9207
41030 59760 3476
5473 46538 6242
726 57718 2589
81784 13867 6400
47816 32769 6817
87193 72489 3704
93767 17119 1251
42745 77820 1433
12227 6357 3305
82388 9...

output:

240727618653011059

result:

ok 1 number(s): "240727618653011059"

Test #51:

score: 0
Accepted
time: 78ms
memory: 19800kb

input:

100000 90002
67217 8067 503
27199 72614 5062
66312 76750 8093
24925 46156 332
89346 96150 726
77009 99274 1729
77684 71042 8646
15347 21451 5933
17929 13651 2478
33381 10670 9392
90209 38279 5783
40403 33152 8674
27171 61467 2831
22091 31557 4900
211 97532 4956
58276 51021 84
61294 32538 2360
26190 ...

output:

215751688196279281

result:

ok 1 number(s): "215751688196279281"

Test #52:

score: 0
Accepted
time: 50ms
memory: 26848kb

input:

100000 10009
20672 90851 9939
88375 47948 1120
20550 41094 5817
21431 82022 152
7104 62820 7738
91360 82649 2605
67904 32597 8405
93248 95318 1180
46520 67938 3533
81182 22789 8230
5046 8819 2664
56743 43474 3719
93395 44698 4417
26363 23229 4721
57848 87655 7821
80439 39603 2397
60613 22289 6164
30...

output:

12103504170679708

result:

ok 1 number(s): "12103504170679708"

Test #53:

score: 0
Accepted
time: 61ms
memory: 27680kb

input:

100000 19999
44373 88130 7730
82690 10159 229
40004 49511 2146
75720 15974 2379
51219 78940 5519
38353 44536 3168
34070 76942 7747
34053 55641 5222
49331 40086 399
47407 98925 5983
76965 8804 2033
40392 60357 1561
57142 83585 1311
49673 19199 6154
811 39827 5326
74418 77037 8927
88012 60611 4517
615...

output:

46596881149793870

result:

ok 1 number(s): "46596881149793870"

Test #54:

score: 0
Accepted
time: 55ms
memory: 26208kb

input:

100000 30010
96242 1527 3036
93256 52144 7485
25217 74320 4254
62982 95272 9991
91193 72811 1299
97734 73574 4134
46762 31809 7325
25793 97512 3275
70127 94215 5513
60599 87028 4324
95738 67331 9521
90998 82709 6745
35246 1945 1389
79687 88728 2564
98294 55694 6303
33261 12160 5881
45777 86967 5810
...

output:

101522055400105731

result:

ok 1 number(s): "101522055400105731"

Test #55:

score: 0
Accepted
time: 57ms
memory: 26964kb

input:

100000 39995
62408 8993 160
68010 79695 2260
68612 46415 3967
24860 71085 3633
30149 37962 7337
19676 62620 2689
14051 193 5206
71628 89950 8154
20649 79829 6097
67343 21061 4912
522 93477 4424
39359 75272 9376
89496 493 3615
26866 56835 6297
39323 57507 9461
66350 22189 1443
89363 12775 4628
17167 ...

output:

173351156580464324

result:

ok 1 number(s): "173351156580464324"

Test #56:

score: 0
Accepted
time: 61ms
memory: 24508kb

input:

100000 50002
2718 10862 9218
24430 79379 8788
99596 12133 7973
25595 6397 3917
92963 65066 6784
64563 79977 458
34400 39878 1590
13029 66657 9202
20795 23693 5952
5184 40872 7262
17199 59824 8571
83986 96844 4219
76626 39140 6744
49866 47065 8453
4151 48035 6927
73108 39390 8230
48703 30889 1785
421...

output:

260687194432990853

result:

ok 1 number(s): "260687194432990853"

Test #57:

score: 0
Accepted
time: 62ms
memory: 25988kb

input:

100000 59992
79166 18875 7133
3666 74564 8770
26548 16271 2317
98609 97471 6999
84090 70982 2169
93443 74047 9555
80223 99334 3003
45842 91203 1168
1295 84030 4427
98783 315 1924
30692 45967 2149
63846 35260 4499
51052 75924 9429
22337 71401 6805
87728 90163 4661
19040 37514 6802
28130 71640 545
509...

output:

359934066042872288

result:

ok 1 number(s): "359934066042872288"

Test #58:

score: 0
Accepted
time: 61ms
memory: 28092kb

input:

100000 70002
43803 79309 2363
122 90496 1536
2548 39161 5649
40761 4683 6632
37327 25423 7436
32291 83803 2749
51152 55290 5436
26969 86691 8885
22312 74553 4831
76271 11171 6937
2429 27049 7429
12532 67033 2847
31434 59936 3314
37875 61138 3323
31421 90723 5024
65513 60041 3269
94818 97279 7154
888...

output:

470460464983222802

result:

ok 1 number(s): "470460464983222802"

Test #59:

score: 0
Accepted
time: 53ms
memory: 28560kb

input:

100000 79992
18830 72145 3936
29938 79225 6076
45618 27045 5908
93597 15134 6749
69609 60450 2958
22705 59428 5964
88011 77093 9970
60223 83668 7312
11741 63792 4437
33247 72684 7683
23408 53635 7637
61529 73686 8926
65708 64096 2147
63200 49011 7533
1755 76316 6825
16639 34984 5805
4149 943 4847
33...

output:

586631135774612069

result:

ok 1 number(s): "586631135774612069"

Test #60:

score: 0
Accepted
time: 66ms
memory: 22748kb

input:

100000 90003
97691 91648 8687
96754 42876 6900
6633 64307 9375
36343 99696 2242
77358 96874 841
16530 23141 1847
7551 47406 2878
79277 60391 8153
69403 21967 4708
6647 18579 4023
87053 80623 5686
85223 18150 6377
30807 72506 9373
6696 44090 7645
73508 93080 3486
82687 90287 3347
12940 50545 1844
157...

output:

708126585659706364

result:

ok 1 number(s): "708126585659706364"

Test #61:

score: 0
Accepted
time: 160ms
memory: 18896kb

input:

100000 9993
71178 28119 9522
98697 66822 5382
37663 35686 3155
97431 95551 7992
58797 71550 9938
73049 38778 6465
54412 949 5691
25835 91619 6227
927 30492 2135
66385 50639 8755
34333 50708 6413
80281 39787 1914
98408 44921 9238
83088 84361 5095
99247 22592 5415
9201 77667 6248
71331 38962 1890
2551...

output:

3843366489686

result:

ok 1 number(s): "3843366489686"

Test #62:

score: 0
Accepted
time: 154ms
memory: 17008kb

input:

100000 19996
25102 5506 4297
91135 6390 8071
28821 68422 1656
28821 6767 7724
49775 68374 5405
34588 93334 8172
54179 30740 6501
51798 4427 5895
5163 28436 1820
80235 5685 2415
57335 13921 1686
29352 8390 3824
94479 9975 4262
93808 73123 2149
70956 21967 3562
88913 39587 1686
45624 93138 1864
44817 ...

output:

16152728265418

result:

ok 1 number(s): "16152728265418"

Test #63:

score: 0
Accepted
time: 146ms
memory: 18068kb

input:

100000 30006
22705 79702 466
60759 71965 3896
84587 15910 850
52324 69155 3693
32624 30570 4652
12508 27601 3094
38233 31900 5977
80201 95015 318
10764 17945 3973
9551 56329 6108
79866 82172 9625
55417 18778 5797
40669 70803 534
56847 58839 7697
25105 81658 8379
42109 15957 9136
46665 71368 1185
745...

output:

36422107318259

result:

ok 1 number(s): "36422107318259"

Test #64:

score: 0
Accepted
time: 158ms
memory: 16652kb

input:

100000 39996
2329 78495 1350
41536 26548 45
66065 76626 3747
29040 71499 9634
74591 49878 4972
28231 25473 9539
42901 93660 7803
57813 26519 4748
83161 40233 4182
1848 67456 4081
19914 67450 8891
75622 23420 2627
90159 92425 9343
62114 76624 6732
26731 71035 9928
94035 83676 4442
45121 50301 9061
58...

output:

53879297010109

result:

ok 1 number(s): "53879297010109"

Test #65:

score: 0
Accepted
time: 151ms
memory: 16752kb

input:

100000 50007
9119 24239 3546
14710 36284 842
40500 21624 6016
3828 65927 1281
33127 27605 3220
32514 84487 6848
59419 77022 5448
34909 78556 9153
5866 3949 476
62613 78838 1033
48158 62430 5637
14322 16505 9989
36784 41113 7871
36355 83475 1831
51864 70071 9618
62468 57697 9578
59535 4636 3856
35986...

output:

87331512109672

result:

ok 1 number(s): "87331512109672"

Test #66:

score: 0
Accepted
time: 158ms
memory: 18104kb

input:

100000 59996
11602 89169 9033
26530 62751 6567
84818 34793 4044
90052 88304 9437
85240 53678 6322
71001 8124 7232
72060 16124 4576
55252 27113 958
4441 96829 2763
86636 75140 2788
56467 6261 6118
70382 29604 590
26463 29663 5677
86392 16047 9126
15407 34146 1285
91948 78526 9205
9284 37319 7117
5460...

output:

104425536558927

result:

ok 1 number(s): "104425536558927"

Test #67:

score: 0
Accepted
time: 152ms
memory: 16648kb

input:

100000 70007
49876 5052 9292
25384 80426 534
69859 65708 5407
35316 35168 8581
79962 61294 4003
15060 92200 6371
33368 72549 8368
49231 34120 6569
22016 67386 1836
32731 8005 8355
85690 19319 934
26466 14495 8247
813 20004 6668
99952 79756 856
37617 64047 3204
44807 83904 1544
27701 63153 1238
10357...

output:

241099094215002

result:

ok 1 number(s): "241099094215002"

Test #68:

score: 0
Accepted
time: 148ms
memory: 17200kb

input:

100000 79993
51103 67613 4713
5559 27036 1916
34440 21158 3981
18783 82945 9307
34664 20 4163
56547 11898 5691
32864 91541 7592
50023 91872 9904
53191 78556 4137
99936 61802 7938
36739 5451 1671
12987 89780 5832
66120 43799 8928
39909 6337 3864
17729 99488 1918
81339 38400 2503
55773 71069 5575
6017...

output:

164644806518908

result:

ok 1 number(s): "164644806518908"

Test #69:

score: 0
Accepted
time: 155ms
memory: 18308kb

input:

100000 90007
17224 11766 5230
33515 87987 7983
24850 85214 8617
48120 47805 2879
54655 61549 4446
30039 69979 659
20848 17048 1699
32365 91937 5524
21870 83857 7486
16829 14432 4209
23618 7486 6493
62831 44399 1098
34639 58315 6607
13030 78890 7925
83615 61180 4698
72956 31177 7729
92318 90690 6706
...

output:

218328806048384

result:

ok 1 number(s): "218328806048384"

Test #70:

score: 0
Accepted
time: 133ms
memory: 15672kb

input:

100000 9990
96107 63486 4703
96107 85337 957
96107 28983 6938
96220 96107 2123
96107 61217 676
87354 96107 2066
96107 49997 9438
96107 27731 2957
49362 96107 3818
96107 24370 6754
73543 96107 2168
11984 96107 4810
96107 38099 6798
96107 69554 2912
96107 14121 4503
98487 96107 6844
44898 96107 9256
4...

output:

949359324753

result:

ok 1 number(s): "949359324753"

Test #71:

score: 0
Accepted
time: 138ms
memory: 15880kb

input:

100000 19996
32968 27062 6055
32968 32816 677
45799 32968 7260
93819 32968 6269
32968 50406 7944
32968 93482 5282
29311 32968 5870
32968 10407 3124
32968 32528 3632
25015 32968 6543
17949 32968 1939
85218 32968 9368
42584 32968 8679
72915 32968 304
8895 32968 5656
32968 60229 884
54229 32968 5957
32...

output:

3596973611730

result:

ok 1 number(s): "3596973611730"

Test #72:

score: 0
Accepted
time: 143ms
memory: 15932kb

input:

100000 30007
95425 603 6030
95425 97146 2748
95425 95150 4697
16077 95425 3763
26316 95425 9836
95425 75423 2457
95425 91616 9995
95425 51265 2201
95425 38912 8008
90255 95425 8123
95425 31400 3203
95425 8895 9547
107 95425 3906
66849 95425 4201
95425 16788 2617
95425 63472 8489
54433 95425 7914
954...

output:

7649970738210

result:

ok 1 number(s): "7649970738210"

Test #73:

score: 0
Accepted
time: 177ms
memory: 15708kb

input:

100000 40001
39334 37807 853
39334 80293 392
73113 39334 4953
39334 49862 3240
39334 17598 3787
39334 89526 1321
70018 39334 5719
97922 39334 1836
83879 39334 8352
18685 39334 1739
1166 39334 7118
86323 39334 8390
55237 39334 6119
39334 51992 5789
12866 39334 7338
747 39334 6850
88149 39334 2044
139...

output:

12801930920000

result:

ok 1 number(s): "12801930920000"

Test #74:

score: 0
Accepted
time: 142ms
memory: 15660kb

input:

100000 50007
55326 94635 3259
55326 37419 1660
55326 14571 9459
68234 55326 9702
54314 55326 8639
11429 55326 7326
29472 55326 7497
55326 65900 446
84575 55326 7141
9790 55326 7245
55326 17863 1074
9140 55326 8363
67414 55326 5345
89235 55326 9381
55326 48082 3957
65977 55326 9287
39323 55326 4404
8...

output:

18767133735834

result:

ok 1 number(s): "18767133735834"

Test #75:

score: 0
Accepted
time: 143ms
memory: 15756kb

input:

100000 60001
40519 41766 6304
40519 57320 5385
40519 31834 4733
40519 78271 366
40519 59104 910
40519 91623 9760
43985 40519 7860
40519 47944 4880
76181 40519 9952
40519 92001 1670
40519 70043 5308
17191 40519 2614
40519 64017 1421
73748 40519 3646
34314 40519 2877
40519 22145 6752
40519 65438 6804
...

output:

25265858100000

result:

ok 1 number(s): "25265858100000"

Test #76:

score: 0
Accepted
time: 148ms
memory: 15736kb

input:

100000 70008
96388 58820 8004
65731 58820 8203
58820 97314 7398
58820 44661 15
69095 58820 982
11507 58820 1524
82862 58820 7039
1342 58820 3548
58820 4595 2375
58820 15027 8031
22701 58820 6805
39748 58820 201
58820 14403 6200
86008 58820 2598
58820 76796 8646
58820 19831 1123
58820 17535 1479
4709...

output:

31907603751331

result:

ok 1 number(s): "31907603751331"

Test #77:

score: 0
Accepted
time: 138ms
memory: 15712kb

input:

100000 80001
15729 47219 2581
47219 1829 9571
562 47219 3024
47219 77306 5093
47219 72540 9707
47219 94724 7828
45673 47219 2031
48493 47219 2264
95594 47219 178
64745 47219 3
1530 47219 8080
85392 47219 774
1185 47219 4998
47219 20797 8917
23318 47219 957
47219 68594 803
47219 77799 821
47219 14603...

output:

38366320960000

result:

ok 1 number(s): "38366320960000"

Test #78:

score: 0
Accepted
time: 128ms
memory: 15696kb

input:

100000 89991
21492 19076 8700
21492 76943 7056
21492 44018 4654
21492 19285 169
46399 21492 5783
99311 21492 1149
90266 21492 2153
89923 21492 4530
21492 99337 6236
61670 21492 4375
62852 21492 7654
21492 63482 6661
23931 21492 4147
91493 21492 5313
96793 21492 7317
21492 70555 7895
21492 18273 6848...

output:

44557775755870

result:

ok 1 number(s): "44557775755870"

Test #79:

score: 0
Accepted
time: 135ms
memory: 16168kb

input:

100000 9990
90001 3279 8345
22307 59642 6990
24535 22656 7790
40884 59247 2512
30205 16853 4292
65239 24515 4440
71621 87010 5767
75802 99107 7613
91909 97447 5064
32887 43572 265
82022 54395 3956
85733 55101 3436
96007 26757 80
74754 51932 2557
73374 79177 8360
24049 77915 3371
88903 39822 7914
525...

output:

214704708935998

result:

ok 1 number(s): "214704708935998"

Test #80:

score: 0
Accepted
time: 128ms
memory: 16120kb

input:

100000 20001
39940 60904 8523
95894 6164 4010
91740 27744 2333
41718 41865 8448
14737 69501 4361
50436 37932 7598
78024 93260 6049
31305 64794 2947
40976 97508 8398
1878 9947 5038
88584 97182 3092
50763 76984 2874
29406 57478 9803
95369 23437 2401
35757 89266 6183
54157 41461 7899
41162 4405 8211
77...

output:

809046226328322

result:

ok 1 number(s): "809046226328322"

Test #81:

score: 0
Accepted
time: 103ms
memory: 16340kb

input:

100000 29995
9508 21006 4451
26200 83026 6421
87546 84725 1613
22123 38529 2618
42539 85753 6654
25478 7260 2680
68926 89374 989
179 73491 6943
96061 9426 6969
87756 4584 9707
71498 73027 6688
44455 49294 2302
28620 53291 8104
30812 12586 406
39185 2758 8224
59799 77250 9553
62026 95807 8555
17605 9...

output:

7080335486904452

result:

ok 1 number(s): "7080335486904452"

Test #82:

score: 0
Accepted
time: 108ms
memory: 16544kb

input:

100000 40001
52670 57633 8373
49135 50624 4000
70791 10973 9486
74022 71717 7879
54748 98824 3194
47287 57802 9191
91142 37496 975
73158 72812 4789
66415 55846 3319
76854 24719 6374
54679 11766 2374
10549 31176 519
4009 58195 3124
94727 55551 2666
51218 97693 7670
78587 82714 594
70234 43008 9259
20...

output:

11876891826947162

result:

ok 1 number(s): "11876891826947162"

Test #83:

score: 0
Accepted
time: 116ms
memory: 16808kb

input:

100000 49991
15468 93970 3453
88725 15397 9983
45516 48497 3602
92305 27398 192
18879 45829 7508
35724 29591 3160
60042 29110 5894
35888 67064 7664
24775 99931 6298
83125 84643 6675
29407 79746 2957
89429 34519 9842
85438 25645 572
59414 84793 6732
28020 8633 1854
92090 92288 2668
36737 42397 5019
5...

output:

18008468119471508

result:

ok 1 number(s): "18008468119471508"

Test #84:

score: 0
Accepted
time: 124ms
memory: 16616kb

input:

100000 60002
47460 6186 9605
96889 29397 1680
26945 16049 6232
65366 78137 9977
63589 88214 2747
54289 133 1417
11486 74326 2719
81062 89912 1534
59328 87956 937
9948 86946 4861
57945 6661 7732
34003 22885 7335
42588 45755 9733
46289 31511 7777
98217 15342 6439
89627 23154 3229
8983 3447 9530
24652 ...

output:

12382588387474094

result:

ok 1 number(s): "12382588387474094"

Test #85:

score: 0
Accepted
time: 119ms
memory: 16468kb

input:

100000 69991
70850 12405 9590
22236 40440 4152
11336 41169 2749
3129 26842 430
55082 50891 1142
37413 8103 9341
56660 52285 1206
2432 54256 8689
26047 23287 9712
75759 39565 2211
12478 1337 9941
67167 23957 4713
78771 18861 6499
54449 2225 914
14954 43204 7221
35243 64736 2030
79961 36776 375
99793 ...

output:

15648141650502096

result:

ok 1 number(s): "15648141650502096"

Test #86:

score: 0
Accepted
time: 119ms
memory: 16392kb

input:

100000 79994
24100 16923 2083
24733 84831 2006
41071 87222 2010
56059 1356 2234
98385 28816 1341
1530 47831 8950
32925 98301 1386
62421 20705 9271
89581 93252 8692
63812 87731 1354
67095 42715 9198
12114 1009 4774
78488 15433 6429
80652 96515 9544
10822 88931 3926
87597 44652 7640
82799 42756 9446
5...

output:

12709850770284554

result:

ok 1 number(s): "12709850770284554"

Test #87:

score: 0
Accepted
time: 121ms
memory: 16496kb

input:

100000 90005
31806 41738 1386
10206 20186 4241
44863 47146 5135
88478 80544 6393
11905 16251 1049
79689 95227 9020
62930 96039 585
19627 80637 725
92166 89467 1422
60566 22584 6353
58071 25097 7346
36531 96712 3475
11582 34111 5726
41184 60227 5050
57031 57305 6214
72576 1251 6989
50694 1631 9095
24...

output:

14586375380631612

result:

ok 1 number(s): "14586375380631612"

Test #88:

score: 0
Accepted
time: 46ms
memory: 26972kb

input:

100000 100000
83021 61980 10000
69109 19742 10000
88130 48834 10000
27084 52869 10000
23114 47237 10000
51287 29136 10000
97795 58207 10000
15061 45653 10000
62750 91657 10000
65590 23616 10000
87386 52974 10000
75125 96444 10000
9110 86157 10000
80797 63703 10000
36243 56445 10000
3279 7747 10000
2...

output:

1666666666500000000

result:

ok 1 number(s): "1666666666500000000"