QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#329974#185. Bridgesjunbin46 1973ms11360kbC++144.9kb2024-02-17 10:07:182024-02-17 10:07:19

Judging History

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

  • [2024-02-17 10:07:19]
  • 评测
  • 测评结果:46
  • 用时:1973ms
  • 内存:11360kb
  • [2024-02-17 10:07:18]
  • 提交

answer

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <list>
#include<fstream>
#include <bitset>

using namespace std;  
using ll = long long;
using ull = unsigned long long;
#define pb push_back
#define P pair
#define V vector
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define FFOR(i, a, b) for (int i = a; i <= b; ++i)

template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
  out << "{"; bool first = true;
  for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
  return out;
}

template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
  out << "["; bool first = true;
  for (auto v : a) { out << (first ? "" : ", "); out << v; first = 0;} 
  out << "]";
  return out;
}

const int N = 200000 + 10;
int ans[N], L[2010], R[2010], timing[N];
bool vis1[N], vis2[N];
vector<int> T[2010];

struct E {
  int u, v, w, t, i;
} e[N], ee[N];

struct Q {
  int u, w, t, i;
  bool operator< (const Q& other) {
    return w > other.w;
  }
} q[N];

bool comp1(E& e1, E& e2) {
  return e1.t < e2.t;
}

bool comp2(E& e1, E& e2) {
  return e1.w > e2.w;
}

//DSU
struct Node {
    int fax, fay, w, sz;
} stk[N];

int p[N], rk[N], sz[N]; 
int top = 0;
int find(int x) {
  return p[x] == x ? x : find(p[x]);
}

bool merge(int u, int v) {
  int fax = find(u), fay = find(v);
  if(rk[fax] > rk[fay]) {
    swap(fax, fay);
  }
  
  //注意这里,否则树的高度会不一样而导致TLE
  if(fax != fay) {
    stk[top++] = (Node){fax, fay, (rk[fax] == rk[fay]), sz[fay]};
    p[fax] = fay;
    sz[fay] += sz[fax];
    if(rk[fay] == rk[fax]) rk[fay]++;
    return true;
  }
  return false;
}

void undo() {
  while(top > 0) {
    top--;
    int fax = stk[top].fax, fay = stk[top].fay;
    p[fax] = fax;
    rk[fay] -= stk[top].w;
    sz[fay] = stk[top].sz;
  }
}
////////////////////////////////////////////////////////////////////

void init(int n) {
  top = 0;
  for(int i = 0; i <= n; i++) {
    p[i] = i, sz[i] = 1, rk[i] = 0, vis1[i] = false;
  }
}

int cnt = 0;
void solve() {
  int n, m;
  scanf("%d%d", &n, &m);
  for(int i = 0; i < m; i++) {
    scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
    e[i].t = 0;
    e[i].i = i;
  }
  
  int k = 0, ti = 0, o = 0;
  scanf("%d", &o);
  for(int i = 0; i < o; i++) {
    int op;
    scanf("%d", &op);
    if(op == 1) {
      int ith, w;
      scanf("%d%d", &ith, &w);
      e[m] = {e[ith - 1].u, e[ith - 1].v, w, ++ti, ith - 1};
      m++;
    } else {
      scanf("%d%d", &q[k].u, &q[k].w);
      q[k].t = ++ti;
      q[k].i = k;
      k++;
    }
  }

  for(int i = 0; i < m; i++) {
    ee[i] = {e[i].u, e[i].v, e[i].w, e[i].t, e[i].i};
  }

  sort(e, e + m, comp1); //按w 从大到小排序
  sort(q, q + k); //按t 从小到大排序

  //分块范围初始化
  int s = sqrt(m);
  int t = 0;
  for(int i = 0; i < m; i += s) {
    L[t] = i;
    R[t] = min(m - 1, i + s - 1);
    t++;
  }
  //分块分配处理
  for(int i = 0; i < k; i++) {
    int j = 0;
    while(j < t && e[R[j]].t <= q[i].t) j++;
    T[min(j, t - 1)].push_back(i);
  }
  
  //for(int i = 0; i < t; i++) cout << i << " " << T[i] << endl;
  
  for(int i = 0; i < t; i++) {
    int l = L[i], r = R[i];
    init(n);
    sort(e, e + l, comp2);
    for(int o = l; o <= r; o++) {
      vis1[e[o].i] = true;
    }

    vector<E> cur;
    int j = 0;
    for(int& x : T[i]) {
      int u = q[x].u, w = q[x].w, idx = q[x].i;
      
      while(j < l && e[j].w >= w) {
        if(e[j].w != ee[e[j].i].w) { //not the newest
        } else {
          if(vis1[e[j].i]) {
            cur.push_back(e[j]);
          } else {
            merge(e[j].u, e[j].v);
          }
        }
        j++;
      }
      
      top = 0;
      for(int o = r; o >= l; o--) {
        if(e[o].t <= q[x].t) {
          if(!vis2[e[o].i]) {
            if(e[o].w >= w) {
              merge(e[o].u, e[o].v);
            }
          }
          vis2[e[o].i] = true;
        }
      }

      for(int o = cur.size() - 1; o >= 0; o--) {
        if(cur[o].t <= q[x].t) {
          if(!vis2[cur[o].i]) {
            if(cur[o].w >= w) {
              merge(cur[o].u, cur[o].v);
            }
          }
          vis2[cur[o].i] = true;
        }
      }

      for(int o = l; o <= r; o++) {
        vis2[e[o].i] = false;
      } 
    
      ans[idx] = sz[find(u)];
      undo();
    }

    for(int o = l; o <= r; o++) { //update edge with the newest info
      ee[e[o].i].w = e[o].w;
    }
  }
  
  for(int i = 0; i < k; i++) {
    printf("%d\n", ans[i] == 0 ? 1 : ans[i]);
  }
}

int main() {
  int t = 1;
  while(t--) {
    solve();
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 13
Accepted
time: 0ms
memory: 4172kb

input:

3 4
1 2 5
2 3 2
3 1 4
2 3 8
5
2 1 5
1 4 1
2 2 5
1 1 1
2 3 2

output:

3
2
3

result:

ok 3 lines

Test #2:

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

input:

7 8
1 2 5
1 6 5
2 3 5
2 7 5
3 4 5
4 5 5
5 6 5
6 7 5
12
2 1 6
1 1 1
2 1 2
1 2 3
2 2 2
1 5 2
1 3 1
2 2 4
2 4 2
1 8 1
2 1 1
2 1 3

output:

1
7
7
5
7
7
4

result:

ok 7 lines

Test #3:

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

input:

5 5
5 3 81
2 4 49
4 1 63
4 3 74
1 2 85
10
2 2 22
2 2 20
1 3 49
2 1 77
1 3 44
1 1 6
2 3 49
2 4 31
2 2 54
2 2 7

output:

5
5
2
4
4
2
4

result:

ok 7 lines

Test #4:

score: -13
Wrong Answer
time: 0ms
memory: 3884kb

input:

5 10
1 3 51
1 2 74
2 4 63
1 4 86
2 5 9
5 1 28
5 4 1
2 1 23
2 5 16
3 1 75
10
2 2 37
1 6 24
1 1 24
2 5 65
1 7 57
2 1 82
2 1 26
1 4 12
2 2 15
1 4 70

output:

4
1
2
4
5

result:

wrong answer 4th lines differ - expected: '5', found: '4'

Subtask #2:

score: 16
Accepted

Test #20:

score: 16
Accepted
time: 1282ms
memory: 9876kb

input:

50000 49999
1 2 976392398
2 3 773336157
3 4 849545817
4 5 194340376
5 6 386778507
6 7 40561907
7 8 260116638
8 9 85673124
9 10 149683208
10 11 724746156
11 12 155084527
12 13 416939763
13 14 753621724
14 15 384948880
15 16 625917615
16 17 833747431
17 18 764302034
18 19 4518648
19 20 405679793
20 21...

output:

7
2
24
1
3
8
1
2
6
2
535
4
3
2
7
13
40
110
3
41
6
1
108
491
28
1
1
4
2
11
5
9
2
1
2
1
9
1
1
3
1
14
3
1
1
10
44
3
2
3
3
1
1
18
3
2
2
2
1
9
1
15
17
7
1
1
1
4
1
2
6
3
1
1
5
1
10
1
5
2
1
14
14
3
28
17
1
6
1
3
1
9
3
10
2
32
54
4
1
2
2
18
1
1
5
1
11
2
10
1
2
5
4
1
1
2
3
4
1
1
128
17
3
1
2
2
1
160
1
1
2
3
...

result:

ok 49863 lines

Test #21:

score: 0
Accepted
time: 1261ms
memory: 9880kb

input:

50000 49999
1 2 491
2 3 15360
3 4 24312
4 5 17754
5 6 40601
6 7 30620
7 8 69533
8 9 144923
9 10 304551
10 11 264913
11 12 265173
12 13 135700
13 14 61571
14 15 6841
15 16 413217
16 17 596083
17 18 157633
18 19 68400
19 20 348725
20 21 494086
21 22 327898
22 23 569190
23 24 195301
24 25 402492
25 26 ...

output:

6
7
16
2
13
24
24
8
1
3
5
257
1
3
6
1
112
2
5
2
11
1
6
2
6
1
1
4
177
7
19
1
1
42
10
2
25
4
24
4
1
3
3
2
1
1
5
1
3
2
13
1
1
1
2
3
5
3
9
2
16
4
10
6
7
3
1
2
17
37
3
1
4
1
4
1
3
7
1
2
2
1
135
3
34
5
2
2
8
2
1
1
1
1
4
3
1
3
2
5
2
1
5
1
2
5
503
3
1
9
7
1
2
4
2
3
5
9
2
15
3
7
9
16
1
28
5
2
5
4
2
3
8
9
4
1...

result:

ok 49979 lines

Test #22:

score: 0
Accepted
time: 1279ms
memory: 9888kb

input:

50000 49999
1 2 20928
2 3 33937
3 4 35582
4 5 123172
5 6 100214
6 7 105156
7 8 46684
8 9 124995
9 10 13728
10 11 209960
11 12 206098
12 13 146953
13 14 370445
14 15 141005
15 16 536276
16 17 80350
17 18 258276
18 19 401626
19 20 32874
20 21 125207
21 22 357075
22 23 598244
23 24 46414
24 25 609917
2...

output:

3
1
1
1
2
1
2
10
7
1
43
3
6
1
4
1
8
1
82
5
3
1
1
2
1
11
5
45
21
1
1
10
2
5
8
2
1
12
1
29
2
1
4
5
2
56
3
3
3
14
1
1
29
9
160
4
3
5
2
2
1
2
6
3
2
11
2
8
1
8
3
3
9
199
1
1
1
1
1
1
1
11
23
2
2
9
339
2
2
1
2
3
1
1
116
6
5
5
10
3
1
1
2
1
18
1
1
6
1
1
8
3
3
1
1
24
1
1
3
1
1
5
12
10
1
6
1
3
2
4
1
2
1
5
6
1
...

result:

ok 50005 lines

Test #23:

score: 0
Accepted
time: 1315ms
memory: 9808kb

input:

50000 49999
1 2 111167988
2 3 402479521
3 4 873342766
4 5 303335487
5 6 357259867
6 7 944570848
7 8 227864068
8 9 137899415
9 10 782881158
10 11 545137901
11 12 125756079
12 13 713912399
13 14 516355545
14 15 306731193
15 16 244028251
16 17 175980262
17 18 956260270
18 19 92690286
19 20 344996907
20...

output:

1
8
1
1
1
1
6
11
21
12
5
3
105
1
1
2
4
5
1
16
1
2
1
3
1
3
2
1
1
2
1
30
2
29
9
8
6
16
1
24
5
8
2
1
5
33
10
12
5
28
10
2
1
1
6
1
2
1
1
1
1
17
7
12
2
3
10
6
2
89
38
2
2
1
2
5
6
1
1
107
47
1
1
1
1
9
1
1
13
2
12
6
1
1
9
9
2
16
1
2
2
2
15
1
4
5
5
1
1
116
5
1
7
5
3
18
1
1
1
14
1
2
1
1
1
3185
1
3
3
2
1
3
7
...

result:

ok 49979 lines

Test #24:

score: 0
Accepted
time: 1351ms
memory: 9900kb

input:

50000 49999
1 2 993457878
2 3 126364173
3 4 200415238
4 5 739704607
5 6 676532686
6 7 557507714
7 8 71727068
8 9 337809709
9 10 681106495
10 11 599345798
11 12 346312387
12 13 39200895
13 14 943426213
14 15 506779546
15 16 379338416
16 17 14615880
17 18 816406736
18 19 211045210
19 20 838922528
20 2...

output:

5
9
18
53
19
1
25
4
19
1
1
1
1
1
11
1
1
2
1
9
1
13
16
5
1
2
1
1
1
7
1
1
16
1
1
5
3
2
3
3
11
2
1
1
12
1
16987
4
12
1
1
1
5
5
5
1
1
4
1
4
2
1
3
1
4
1
1
2
5
2
18
1
3
200
1
4
2
7
1
1
1
2
44
2
1
10
11
2
3
12
1
3
4
10
4
7
1
16
6
1
13
4
1
5
3
2
1
2
2
2
1
31
40
3
2
1
3
1
86
2
2
1
1
1
1
15
2
1
1
1
6
1
1
7
1
...

result:

ok 50005 lines

Test #25:

score: 0
Accepted
time: 1450ms
memory: 10892kb

input:

50000 49999
1 2 2180
2 3 39922
3 4 2857
4 5 41405
5 6 71574
6 7 34628
7 8 271216
8 9 134571
9 10 77206
10 11 98084
11 12 86039
12 13 449514
13 14 490107
14 15 450572
15 16 139688
16 17 639236
17 18 247981
18 19 75121
19 20 300881
20 21 7682
21 22 248842
22 23 599408
23 24 647942
24 25 7276
25 26 470...

output:

49496
49499
49314
30098
32346
32346
49499
30098
42345
4779
49496
42345
49314
32346
49496
49314
30098
1640
30098
30098
30098
6969
6968
40954
49314
30098
2248
30098
30098
403
40954
6969
49314
6969
30098
49498
30098
4779
40954
49499
6968
42345
30098
32346
1345
32346
49314
32346
40954
32346
6969
6969
33...

result:

ok 49911 lines

Test #26:

score: 0
Accepted
time: 1452ms
memory: 10664kb

input:

49999 49998
1 2 2541
2 3 57948
3 4 37666
4 5 66268
5 6 42284
6 7 115405
7 8 248366
8 9 262167
9 10 145846
10 11 47627
11 12 431021
12 13 218051
13 14 401077
14 15 549059
15 16 169347
16 17 363982
17 18 490171
18 19 370535
19 20 480055
20 21 327730
21 22 278018
22 23 231965
23 24 256156
24 25 329573
...

output:

450
33828
47494
47494
1249
47493
9064
9064
24764
8175
47493
8175
33828
19203
19203
3968
1811
8175
5561
1689
42003
8175
33828
42003
33828
47494
19203
5561
24764
47494
3968
16782
24764
19203
24764
47494
24764
8175
24764
47493
9064
75
9064
1689
47494
1689
1689
24764
5561
2976
33828
3968
33828
78
24764
...

result:

ok 50105 lines

Test #27:

score: 0
Accepted
time: 1435ms
memory: 10568kb

input:

49999 49998
1 2 23701
2 3 57539
3 4 70283
4 5 136271
5 6 141212
6 7 184696
7 8 228429
8 9 29895
9 10 31218
10 11 282781
11 12 29995
12 13 131524
13 14 133988
14 15 197273
15 16 351724
16 17 391575
17 18 253620
18 19 611546
19 20 216997
20 21 305541
21 22 118275
22 23 306021
23 24 482979
24 25 709132...

output:

26373
8528
1944
10472
1430
6356
3806
5934
1944
49998
8528
11437
369
363
36932
4327
3351
3351
3806
6496
1944
49973
5934
13041
19188
1857
652
2143
13254
13254
12975
49998
599
8528
1944
10472
5934
8528
19
10472
13254
10472
1935
4327
6356
11339
36932
13254
10472
4257
3806
610
6496
5934
2220
11437
1300
4...

result:

ok 50026 lines

Test #28:

score: 0
Accepted
time: 24ms
memory: 5932kb

input:

1 0
100000
2 1 710454586
2 1 30174257
2 1 685675008
2 1 417816804
2 1 327755609
2 1 841371333
2 1 301370841
2 1 143821498
2 1 232099091
2 1 977178764
2 1 572665966
2 1 913418066
2 1 808399404
2 1 22331931
2 1 434460344
2 1 40437984
2 1 997406768
2 1 40071081
2 1 268638772
2 1 541398526
2 1 983507437...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 100000 lines

Test #29:

score: 0
Accepted
time: 667ms
memory: 10276kb

input:

50000 49999
1 2 2
2 3 2
3 4 1
4 5 2
5 6 2
6 7 1
7 8 1
8 9 2
9 10 2
10 11 1
11 12 1
12 13 2
13 14 1
14 15 1
15 16 1
16 17 1
17 18 1
18 19 2
19 20 2
20 21 1
21 22 2
22 23 1
23 24 1
24 25 1
25 26 1
26 27 1
27 28 2
28 29 2
29 30 2
30 31 2
31 32 1
32 33 1
33 34 2
34 35 2
35 36 2
36 37 2
37 38 2
38 39 1
3...

output:

50000
50000
50000
50000
6
2
2
50000
50000
50000
50000
50000
50000
6
50000
1
1
50000
50000
4
4
50000
1
50000
50000
3
50000
2
50000
2
3
50000
1
50000
4
50000
50000
4
50000
50000
5
50000
9
50000
50000
10
3
5
50000
1
50000
50000
50000
50000
1
50000
50000
50000
3
50000
2
3
1
50000
50000
50000
50000
3
500...

result:

ok 49970 lines

Test #30:

score: 0
Accepted
time: 645ms
memory: 10092kb

input:

50000 49999
1 2 2
2 3 2
3 4 2
4 5 2
5 6 1
6 7 3
7 8 1
8 9 3
9 10 3
10 11 1
11 12 3
12 13 2
13 14 2
14 15 2
15 16 3
16 17 3
17 18 3
18 19 1
19 20 2
20 21 3
21 22 1
22 23 2
23 24 1
24 25 3
25 26 3
26 27 3
27 28 3
28 29 3
29 30 3
30 31 1
31 32 3
32 33 1
33 34 2
34 35 2
35 36 2
36 37 1
37 38 3
38 39 1
3...

output:

50000
1
1
50000
50000
1
50000
50000
1
3
1
2
6
50000
50000
50000
50000
2
2
4
2
50000
5
3
50000
8
1
1
3
2
50000
50000
2
9
1
50000
50000
5
50000
1
7
50000
50000
6
1
9
5
4
4
1
3
50000
1
50000
3
2
2
50000
2
50000
4
5
50000
1
4
50000
5
50000
7
3
3
6
2
50000
3
12
50000
2
2
50000
9
50000
5
50000
50000
50000...

result:

ok 50021 lines

Test #31:

score: 0
Accepted
time: 859ms
memory: 9600kb

input:

49999 49998
1 2 17203
2 3 2847
3 4 78198
4 5 153265
5 6 167348
6 7 223540
7 8 247201
8 9 165110
9 10 39406
10 11 169131
11 12 77633
12 13 189498
13 14 426647
14 15 370032
15 16 150693
16 17 137818
17 18 532098
18 19 516136
19 20 378632
20 21 155025
21 22 514837
22 23 297354
23 24 420776
24 25 391135...

output:

16669
3311
16669
16669
27851
626
13228
12829
2938
43909
399
2604
27851
10120
442
16669
13228
3783
3311
12829
16669
4348
27851
673
3311
624
12829
208
4348
4398
16669
2830
16669
16669
16669
16669
16669
10120
16669
1063
1424
13228
16669
16669
624
1424
2604
16669
16669
12829
12829
10120
12829
21017
2107...

result:

ok 89927 lines

Test #32:

score: 0
Accepted
time: 1956ms
memory: 11360kb

input:

49999 49998
1 2 15625
2 3 58909
3 4 79176
4 5 78230
5 6 108291
6 7 91661
7 8 34888
8 9 86333
9 10 196105
10 11 339006
11 12 66021
12 13 415608
13 14 107020
14 15 197675
15 16 190986
16 17 61241
17 18 430747
18 19 10073
19 20 696099
20 21 681217
21 22 687623
22 23 216763
23 24 8263
24 25 341165
25 26...

output:

208
53
4539
359
704
2952
7275
15294
1317
8926
49868
9467
10243
49868
9467
8926
4254
1224
2952
1463
4254
9467
10243
4539
9467
7275
29898
10243
9467
11529
2253
9467
7275
29898
9467
29898
9467
7275
4254
9467
40141
1127
45624
47145
519
1288
4254
40141
2952
49999
7275
29898
2952
10243
7275
40141
640
6918...

result:

ok 9962 lines

Subtask #3:

score: 17
Accepted

Test #33:

score: 17
Accepted
time: 974ms
memory: 8992kb

input:

32767 32766
1 2 152523690
1 3 736211233
2 4 163158345
2 5 200010458
3 6 902682843
3 7 427399287
4 8 770411775
4 9 322256303
5 10 252775416
5 11 346597970
6 12 297314023
6 13 727299741
7 14 985621564
7 15 101953231
8 16 405434218
8 17 421655547
9 18 817411034
9 19 310455840
10 20 355126049
10 21 7038...

output:

1
1
2
2
6
6
12547
1
1
1793
3
41
1
37
29734
8197
1
1
1
2
11
3
7
5
18
39
13
136
1
2
1
1
4
2
177
3
279
2
36
114
53
4
9
3
2
1
21
6
2
2
5
2
1
6
7
1
5
4
11
23129
288
196
8
1
5
9
3
1
4
45
4
1
1
5
3
3
10
18
91
1
16
829
24
1
2
8
1247
10
2
1
7
20323
8
1
2
28551
1
6
1
12
4
3
1
27
1
1
1
1
2
3
1
7
1
487
1
21
15
...

result:

ok 50019 lines

Test #34:

score: 0
Accepted
time: 535ms
memory: 7656kb

input:

8191 8190
1 2 217141764
1 3 529497259
2 4 779147272
2 5 691696039
3 6 48118037
3 7 603814603
4 8 696908741
4 9 217271102
5 10 68704258
5 11 22697519
6 12 683544026
6 13 723792342
7 14 793130995
7 15 92576446
8 16 327755609
8 17 103625834
9 18 543827967
9 19 341371333
10 20 640187172
10 21 85328878
1...

output:

3231
8191
580
3382
8191
8191
8191
8191
3212
6
4
7
6
3187
6120
6152
4
457
8191
7
2
8191
8191
8191
8191
8191
4
8191
8191
8191
8191
3605
8191
7
8191
5715
6975
8191
8191
4289
2
8191
6977
8191
2
8191
8191
4
1
1
8191
1
8191
8191
11
8191
8191
222
1
8191
5905
8191
8191
8060
8191
8191
8191
2
1
8191
8191
8191...

result:

ok 49969 lines

Test #35:

score: 0
Accepted
time: 980ms
memory: 9020kb

input:

32767 32766
1 2 217141764
1 3 529497259
2 4 762168910
2 5 862501617
3 6 287569355
3 7 60434037
4 8 741381891
4 9 846044727
5 10 559556243
5 11 841922729
6 12 260807264
6 13 108798675
7 14 165384865
7 15 803171234
8 16 680929744
8 17 534495504
9 18 618761142
9 19 633256718
10 20 244069182
10 21 40934...

output:

32767
32767
32767
32767
32767
32767
32767
32767
32767
32767
3
32767
16965
32767
2
26
32767
32767
6
1
32767
7826
32767
1
21971
7
32767
12668
5289
162
32767
15263
32767
11
32767
3
4
32767
18
118
32767
1
32767
32767
32767
5
32767
32767
39
32767
267
32767
32767
32767
32767
32767
1
7
32767
2
32767
1
228
...

result:

ok 50058 lines

Test #36:

score: 0
Accepted
time: 933ms
memory: 9056kb

input:

32767 32766
1 2 960028533
1 3 932018255
2 4 966739858
2 5 978817181
3 6 951511415
3 7 993940257
4 8 988418327
4 9 995978961
5 10 810804356
5 11 990996089
6 12 988830283
6 13 964972868
7 14 860937540
7 15 840655680
8 16 840257957
8 17 761892560
9 18 901480224
9 19 889396012
10 20 884899819
10 21 9367...

output:

5
1
6
19293
1
17937
1
1
1
1
1
3
7
1
4
6883
32026
1
1
1
2
5824
2
19
2
28839
7
1
8
12099
19229
27469
2
3
1
10692
1
21275
1
2
1
31
1
1
1
15551
1
1
1
32498
7
31105
29865
1870
31927
1
3
1
1
1
1
27524
1
9
29426
4
1
12
4
26271
1
18126
2
1
1
1
1
31028
6
8
14285
1
3103
3
2
8
2
31181
1
1
1
21314
1
7
2
1
1
244...

result:

ok 50058 lines

Test #37:

score: 0
Accepted
time: 25ms
memory: 5924kb

input:

1 0
100000
2 1 710454586
2 1 30174257
2 1 685675008
2 1 417816804
2 1 327755609
2 1 841371333
2 1 301370841
2 1 143821498
2 1 232099091
2 1 977178764
2 1 572665966
2 1 913418066
2 1 808399404
2 1 22331931
2 1 434460344
2 1 40437984
2 1 997406768
2 1 40071081
2 1 268638772
2 1 541398526
2 1 983507437...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 100000 lines

Test #38:

score: 0
Accepted
time: 1013ms
memory: 9408kb

input:

32767 32766
1 2 304863256
1 3 602102863
2 4 381894905
2 5 32190927
3 6 257274874
3 7 843197505
4 8 480275676
4 9 93549775
5 10 363411747
5 11 765890415
6 12 610483185
6 13 451529600
7 14 654899236
7 15 24173250
8 16 387501501
8 17 763650861
9 18 561615412
9 19 651242897
10 20 715964996
10 21 1542732...

output:

930
34
28341
6
1
2273
3373
19210
1
1
301
1
3410
1
1
1
24965
24019
1
5974
59
1
1
1
1
22
4307
12766
1192
17423
12976
6
1
29017
1
1
11
5
12750
5
21457
101
16242
4
1
47
17642
5
63
6
26577
46
22993
1
2
114
20
31591
31858
3
1
30277
1
29617
48
1
1
18339
536
3
21832
22066
4364
1
2
17629
1167
1475
7
39
1
542...

result:

ok 50054 lines

Test #39:

score: 0
Accepted
time: 930ms
memory: 9300kb

input:

32767 32766
1 2 482946680
1 3 880684411
2 4 486062030
2 5 753631684
3 6 451749132
3 7 539244314
4 8 295789966
4 9 353762227
5 10 461289276
5 11 473918705
6 12 516181394
6 13 29129197
7 14 223169542
7 15 734712283
8 16 7164799
8 17 100959247
9 18 777798154
9 19 145416338
10 20 51605940
10 21 47461960...

output:

24646
1
1
1
27208
1
1
1
1
1
18717
1
1
1
1
48
1
1
2
2
1032
1
1
43
1
1
2
1
3
3
1
1
1
2
1
1
1
1
1
3
1
6
89
1
1
2
1
1
1
8000
1
1
1
1
1
31
1
1
738
1
30766
169
1
1
1
21393
1
28018
676
13
1
1
7
1
21387
1
12
29352
1
28377
21175
2
1
1
1
22940
21
1
1
1
1
1
2
1
1
1
1
1
1
1
1
32
22032
1
9
1
7263
1
1
33
1
1
1
1
...

result:

ok 50075 lines

Test #40:

score: 0
Accepted
time: 942ms
memory: 9020kb

input:

32767 32766
1 2 366062808
1 3 603976360
2 4 590229156
2 5 800736806
3 6 44097753
3 7 328945174
4 8 557936610
4 9 632480701
5 10 577672826
5 11 200453016
6 12 431132615
6 13 454618640
7 14 648582705
7 15 122970083
8 16 30025754
8 17 207861161
9 18 192145853
9 19 75028951
10 20 136159383
10 21 3917683...

output:

1
1
1
3
12609
1
1
4
2
1
2
19058
4
1
1
82
1
166
1
97
1
1
1
1
1
1
12
1
3
73
1
1
1
2
1
3
1
7
1
1
4
34
1
1
1
1
506
1
1
13
1
1
1
28624
1
1
1
1
1
1
1
1
1
8946
6
1
1
1
1
1
1
1
1
1
1
1
1
1
1
75
1
1
4
555
10
1
1
1
1
1
24094
1
1
1
1
1
1
1
22
480
1
25777
2
876
1
1
1
1
1
1
1
1
27951
27
6
1
1
21092
3
4
5
2
1
1
3...

result:

ok 50060 lines

Test #41:

score: 0
Accepted
time: 470ms
memory: 8236kb

input:

32767 32766
1 2 526218806
1 3 574084493
2 4 237859344
2 5 141452753
3 6 368924609
3 7 637004921
4 8 605655343
4 9 693060207
5 10 774267027
5 11 361913571
6 12 246425613
6 13 652046016
7 14 732152503
7 15 405990171
8 16 78495161
8 17 295900332
9 18 621532297
9 19 550041506
10 20 590380095
10 21 42581...

output:

2
9
1
1
780
31162
395
5
20000
3
1
31
18076
1
12543
2
1
28058
15999
5
1
14
2
11
15
14505
1
3
12955
1
10641
8590
11525
28146
2
1
1
11
10393
1
1
4326
4
3749
30823
30864
190
2
26697
4
4702
31152
12
17512
19553
4
6361
1
1
22438
1
1
22440
308
1
5
3
10677
1
1
2
2
14183
273
104
177
161
2
174
1
1
113
1
12452...

result:

ok 90025 lines

Test #42:

score: 0
Accepted
time: 416ms
memory: 8428kb

input:

32767 32766
1 2 954543458
1 3 18121943
2 4 30728674
2 5 916608595
3 6 412861262
3 7 616231888
4 8 27230960
4 9 800190746
5 10 491548327
5 11 276864792
6 12 681168067
6 13 220316323
7 14 129663315
7 15 727981026
8 16 567913703
8 17 92764660
9 18 131826495
9 19 268199078
10 20 544330589
10 21 41005757...

output:

3
2
2
1
3
1
1
5
56
5296
1
4
1
4
1
1
1236
1
22
5
19966
2
12
6
475
28586
1
264
1
1027
1
1
3
1
1
1
1
27701
21136
1
1
1
5011
1
1
1
1
1
1
1
1
1
1
71
3
1
24884
26896
1
1
3
27180
1011
4
1
1
3
5
1
1154
1
1
1
1
27
8552
1
1
9
30626
3
1
3
2092
1
767
1
1
5
1
1
1
29
37
1
2
1
9
4
1
1
1
4
1
1
1
6
31609
7489
1
1
5
...

result:

ok 90104 lines

Test #43:

score: 0
Accepted
time: 1502ms
memory: 9900kb

input:

32767 32766
1 2 750306444
1 3 886768475
2 4 651477786
2 5 780811636
3 6 879514155
3 7 639920406
4 8 827906566
4 9 246759076
5 10 8902446
5 11 483498857
6 12 311018275
6 13 112196172
7 14 814260430
7 15 672877709
8 16 372626021
8 17 522011729
9 18 598389201
9 19 551905942
10 20 529431530
10 21 234869...

output:

1
25043
8
1
2
1
1
28474
3
1
69
1
6
5173
3
1
1
17360
2
36
52
12
31042
9682
24455
1
1028
1
1
174
16865
16070
12
9
21
1297
7994
28249
19546
25190
3
2
1
12895
1
14822
10669
3
43
26915
3
19
3
3269
8968
26
17515
1
3041
12143
28763
8
450
1
28
17049
1
1
162
10365
1
15990
3
1
3
1
1
1
8461
1
1
1
32132
32
1
22...

result:

ok 9964 lines

Test #44:

score: 0
Accepted
time: 1532ms
memory: 9508kb

input:

32767 32766
1 2 323855288
1 3 625773221
2 4 698582907
2 5 373160258
3 6 923450808
3 7 619147373
4 8 240229172
4 9 353889615
5 10 583326603
5 11 398450078
6 12 262116331
6 13 537609336
7 14 676909617
7 15 593611072
8 16 76330278
8 17 774996257
9 18 145485185
9 19 636459385
10 20 64063610
10 21 255915...

output:

1
31283
1
1
7274
1
1
3
1
1
1
1
1
11
1
16354
1
60
1
30681
9
24
16
1
3
20953
1
1
1
25886
30028
1
2
4
1
1
398
1
14992
25644
27541
4
1
1
1
2
1
26449
1
1
35
1
30707
1
1
187
1
1
119
1
214
12795
1346
1
1
1
2051
301
692
1
11198
19
7101
125
2
1
1
59
1
1
13466
26746
29152
1
1
1
164
2
20139
20192
2
7
1
1
16823...

result:

ok 10060 lines

Subtask #4:

score: 0
Time Limit Exceeded

Test #45:

score: 0
Time Limit Exceeded

input:

50000 100000
35231 1616 822934828
1668 2202 768458723
26049 41810 238904165
15936 42751 466996423
41068 21425 588205829
29502 11760 732391267
13029 44741 930695124
46168 22085 155239713
9505 43779 638894800
18665 43842 298794735
41763 15511 727702105
7865 27776 53447691
32904 34081 844499614
26327 9...

output:


result:


Subtask #5:

score: 13
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #68:

score: 13
Accepted
time: 1289ms
memory: 9876kb

input:

50000 49999
1 2 773336157
1 3 194340376
1 4 40561907
2 5 85673124
3 6 724746156
1 7 416939763
4 8 384948880
7 9 833747431
1 10 4518648
3 11 311221494
5 12 578773527
3 13 320772778
4 14 11680621
14 15 852209440
1 16 532930901
2 17 616508554
12 18 658403193
12 19 366813101
5 20 276295000
7 21 83097661...

output:

34145
2
2
1630
1
2
2
7
4
1
2
1
4
1
48
1
153
1
2
1226
3
24
8
3
1
1
1
1
1
1
82
4
8394
2
19
3
1
1
36647
1
2
2
1
1
2900
14
1
2
1
18
1
13
2
12501
1
16
1
21
20073
262
2
4
5
10
3
1
2
4
1
29
8437
35
1
1550
1
1473
1
2
1
6
13
1
8726
18
17
153
26389
28
3
1
1
2
1
3
94
20
23
1
56
1
1
2
1
1
1
19
5
1
2
13
3
4
1
6
...

result:

ok 49883 lines

Test #69:

score: 0
Accepted
time: 1350ms
memory: 9900kb

input:

50000 49999
541 8680 217141764
42411 17450 29497259
2922 2367 210454586
42888 46242 141218013
31513 12691 39075415
14443 43750 30174257
32433 2083 24849107
22052 28722 218638133
44265 1646 185675008
30107 2335 20621009
12541 33175 339804815
4109 316 167816804
46420 2599 138763480
1373 39613 11005866...

output:

50000
50000
50000
1253
50000
50000
511
50000
91
21518
50000
50000
24240
50000
50000
5
50000
50000
45135
50000
45876
5742
50000
50000
1
1
2
12346
30
11109
50000
50000
1
50000
4
48872
50000
16
1
50000
50000
2135
50000
50000
1
50000
1
50000
50000
6
50000
71
1
1
50000
50000
2
50000
50000
50000
50000
500...

result:

ok 49970 lines

Test #70:

score: 0
Accepted
time: 1308ms
memory: 10124kb

input:

50000 49999
36327 41883 688572006
21929 4974 528312959
19046 37544 265073551
28063 18603 590341643
12826 32116 630808478
42426 34818 797944744
30992 11239 756872548
16594 9393 347055714
12923 27255 728101884
3466 38095 985921549
30066 45072 313790123
12786 26083 675676126
10051 9213 336178036
30649 ...

output:

1
1
56
5
1
5085
1
2
19
2
1
1
1
3
2
46796
3
29
1
1
13
3
39764
22
47506
1399
1
76
48082
28
4
15
3
85
1
2
1
1
1
1
44571
1
1
10969
2
1316
8
1
1816
1
1
2
1
45
1
219
13257
1
48948
4
1
23
43961
3
1
80
13
1
349
1
1
1
3
48821
1
2436
1
12
4
1
3679
1
48942
12077
1
47
2
22481
47568
1
2
3
45910
10
7
2
4
2
47932
...

result:

ok 49970 lines

Test #71:

score: 0
Accepted
time: 1203ms
memory: 10000kb

input:

50000 49999
45356 46055 222229657
18891 14106 46041344
6216 9336 108993111
11065 34146 43768553
45232 30811 143991316
42200 33069 48849452
44364 1111 75772099
23278 17601 170969223
9916 4521 164287252
25192 3255 273246573
39276 28125 308565624
46267 40316 7392430
27354 7565 142314468
22639 42466 198...

output:

1
1
1
1
1
1
1
1
11
1
1
1
1
1
1
1
10
1
1
1
1
1
3
2065
1
1
1
1
1
14
1
2
1
6
12034
1
3
1
1
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
46655
12
1
42969
1
1
1
1
1
1
3
1
1
1
1
1
2
1
3
1
1
1
1
1
1
1
34920
1
1
8
1
1
1
1
1
2
1
12
1
1
1
1
1
1
1
1
4
1
1
1
1
1
1
3839
1
26988
1
1
1
1
1
1
1
1
1
1
1
45262
1
12
1
1
1
1
1
1
1
...

result:

ok 50014 lines

Test #72:

score: 0
Accepted
time: 1372ms
memory: 9912kb

input:

50000 49999
45895 3922 71902426
21874 14474 197348243
39626 34823 51434808
5189 6472 12708634
36193 1872 58453465
26063 7150 141846401
18760 28835 38331526
32874 21952 145776113
1122 49427 87692578
41696 3543 95256733
7963 500 32486178
16249 41532 71644540
26431 19428 274682273
34698 31060 149686448...

output:

2
10
2
4
1
50000
11
3
18
50000
1
1
50000
11
2
6
2
1
50000
33
50000
50000
22
50000
1
50000
4
6
2
2
2
5
18
1
2
2
20
2
1
50000
6
1
71
194
50000
2
50000
50000
54
6
50000
2
25
50000
5
18
3
57
3
14
33
31
1
6
62
3
9
147
10
356
44
5
7
10
2
50000
50000
1
27
3
7
50000
50000
50000
1
2
3
2
2
50000
5
50000
50000...

result:

ok 49970 lines

Test #73:

score: 0
Accepted
time: 1375ms
memory: 9840kb

input:

50000 49999
35341 13520 17141764
26545 49269 29497259
16246 22640 110454586
35433 46589 141218013
5786 1083 189075415
4466 48857 30174257
11816 6000 24849107
3107 31468 68638133
19886 14823 85675008
48925 7887 70621009
32929 10764 39804815
27178 8517 417816804
26641 43632 38763480
35866 38748 110058...

output:

7
5
12
1
1
5
1
50000
2
50000
50000
6
22
50000
2
50000
50000
4
4
2
1
50000
2
1
106
31
57
31
1
13
50000
50000
50000
52
50000
1
260
50000
4
50000
1
3
50000
29
50000
11
15
2
13
1
81
50000
19
50000
50000
25
6
50000
50000
12
6
5
5
10
4
1
50000
5
6
6
1
50000
4
50000
25
2
5
50000
50000
4
2
8
50000
3
81
354
...

result:

ok 49970 lines

Test #74:

score: 0
Accepted
time: 1389ms
memory: 9884kb

input:

50000 49999
25529 24861 71902426
32875 12248 86237132
15921 39212 273657030
28320 39686 123819745
35421 694 58453465
14424 5372 141846401
1812 36451 149442637
6965 15454 145776113
4884 14172 87692578
35538 26406 95256733
22100 30598 143597289
14130 47258 182755651
17570 17146 52460051
22098 17556 14...

output:

2
2
3
7
5
50000
58
9
30
4
1
1
4
50000
8
1
20
1
3
50000
1
50000
30
16
5
50000
24
2
50000
2
3
1
2
1
14
50000
34
50000
22
1
50000
36
80
236
1
50000
7
50000
18
50000
6
2
17
4
6
12
2
38
50000
2
74
4
2
50000
136
50000
1
114
2
50000
50000
3
2
15
1
4
50000
6
16
1
7
50000
50000
31
8
6
9
50000
1
202
4
50000
1...

result:

ok 49970 lines

Test #75:

score: 0
Accepted
time: 1325ms
memory: 10168kb

input:

50000 49999
45895 3922 556486138
21874 14474 500239109
39626 34823 813918810
5189 6472 676494674
36193 1872 630808478
26063 7150 457864078
18760 28835 11366687
32874 21952 788882333
1122 49427 933153048
41696 3543 184270819
7963 500 759242048
16249 41532 933865474
26431 19428 814065727
34698 31060 4...

output:

2
137
2
2
7
4
4
9
11
7
1
2
1
1
2
11
105
5
1
1
8
7
3
1
1
1
20
1
2
27
3
1
4
3
1
1
6
4
1
2
1
7
2
6
1
76
43
1
1
5
1
7
1
1
29
1
1
2
1
1
6
1
4
6
2
26
5
2
5
1
1
1
2
7
2
36
1
4
5
1
1
2
49494
1
1
2
3
4
18
8
2
5
25
42
15
8
1
2
48982
2
1
1
2
4
5
4
2
111
1
1
1
1
1
8
2
4
1926
11
1
3
6
2
13
3
1
3
2
1
1
2
33
1
2
1...

result:

ok 49970 lines

Test #76:

score: 0
Accepted
time: 1305ms
memory: 9880kb

input:

50000 49999
35341 13520 695714444
26545 49269 528312959
16246 22640 914303724
35433 46589 698821037
5786 1083 734408363
4466 48857 690584088
11816 6000 609868641
3107 31468 347055714
19886 14823 728101884
48925 7887 557096411
32929 10764 133121824
27178 8517 765140958
26641 43632 336178036
35866 387...

output:

3
2
1
27
1
4
6
2
1
1
1
1
42
1
8
129
1
18
1
23
5
1
2
2
1
98
1
1
5
1
1
1
44
1
3
13
1
1
1
1
2
1
1
1
1
5
2
11
3
5
1
8
1
1
1
3
22
1
49373
2
4
8
1
3
1
2
3
2
1
1
4
1
111
49287
1
1
4
1
2
8
1
10
49369
2
1
8
1
3
48519
1
6
2
2
3
2
1
4
1
2
1
1
21
91
1
1
4
5
1
1
7
1
145
1
6
10
4
1
1
3
252
1
2
1
3
1
1
47
13
2
5
1...

result:

ok 49970 lines

Test #77:

score: 0
Accepted
time: 1315ms
memory: 10152kb

input:

50000 49999
25529 24861 454246504
32875 12248 528312959
15921 39212 584049702
28320 39686 398236797
35421 694 630808478
14424 5372 779472977
1812 36451 866549529
6965 15454 788882333
4884 14172 933153048
35538 26406 184270819
22100 30598 126730895
14130 47258 485611323
17570 17146 482753900
22098 17...

output:

3
133
1
4
5
7
168
10
6
2
215
1
14
2
2
2
1
1
3
1
1
1
1
1
1
1
39
1
48792
22
2
2
70
1
1
1
1
3
2
5
41
4
2
2
3
8
1
1
1
1
10
1
2
1
5
1
4
8
49329
3
2
9
1
8
2
1
2
1
6
102
1
19
2
7
1
2
3
6
124
1
2
1
49329
3
84
22
4
2
3
1
2
1
15
4
1
2
173
2
48672
3
1
2
2
4
4
5
2
3
2
2
13
1
142
2
1
1
2
6
2
1
1
25
1
3
8
3
72
1
...

result:

ok 49970 lines

Test #78:

score: 0
Accepted
time: 1240ms
memory: 9980kb

input:

50000 49999
45895 3922 259666452
21874 14474 99678318
39626 34823 34014426
5189 6472 88980800
36193 1872 98545108
26063 7150 257073367
18760 28835 96275478
32874 21952 10925241
1122 49427 131362924
41696 3543 7390389
7963 500 47191743
16249 41532 212104466
26431 19428 34881854
34698 31060 24950387
2...

output:

10
1
4
1
2
1
1
1
1
1
1
4
5
7
2
1
1
1
6
1
1
1
40
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
11
1
1
1
1
4
1
1
12
1
2
4
2
48
571
3
1
2
1
1
1
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
7
2
1
1
1
4
1
1
2
1
24
13
1
1
3
1
1
1
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
2
1
2
1
3
1
1
1
1
1
1
1
1
4
2
1
1
1
2
1
1
1
1
78
1
3
1
1
1
5
1
1
1
1
1
1
...

result:

ok 50014 lines

Test #79:

score: 0
Accepted
time: 1219ms
memory: 9940kb

input:

50000 49999
35341 13520 22229657
26545 49269 46041344
16246 22640 158993111
35433 46589 93768553
5786 1083 143991316
4466 48857 248849452
11816 6000 175772099
3107 31468 20969223
19886 14823 64287252
48925 7887 73246573
32929 10764 8565624
27178 8517 7392430
26641 43632 92314468
35866 38748 11985288...

output:

1
1
5
4
1
1
13
1
7
6
1
1
1
3
11
1
1
1
1
1
1
1
1
3
1
1
2
1
133
8
1
1
1
3
6
1
1
1
1
1
23
1
1
1
2
2
2
1
1
1
1
1
1
1
2
188
1
1
94
1
1
1
1
2
22
1
1
1
1
24
1
2
2
9
10
1
1
1
12
1
1
8
1
1
1
11
1
1
1
1
1
1
1
1
1
1
1
4
44
1
1
1
1
1
1
1
1
4
9
1
30
1
1
1
1
1
2
1
1
1
34
1
349
1
1
3
1
1
1
1
1
1
1
1
1
1
5
1
1
1
1
...

result:

ok 50014 lines

Test #80:

score: 0
Accepted
time: 1204ms
memory: 10144kb

input:

50000 49999
25529 24861 148555341
32875 12248 99678318
15921 39212 367347759
28320 39686 422314133
35421 694 98545108
14424 5372 145962256
1812 36451 207386589
6965 15454 10925241
4884 14172 131362924
35538 26406 7390389
22100 30598 158302854
14130 47258 323215577
17570 17146 34881854
22098 17556 24...

output:

1
1
1
1
1
1
1
1
1
1
1
1
5
8
1
1
1
1
1
1
1
1
1
1
1
2
1
1
10
1
1
1
1
1
1
1
1
1
1
4
1
3
1
1
1
1
1
7
1
1
1
1
14
243
1
10
1
1
1
1
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
5
1
1
1
1
1
47
1
1
5
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
3
1
1
1
1
2
1
1
1
1
1
1
1
1
1
2
1
1
1
1
1
1
1
1
44
13
2
1
1
1
5
1
1
1
1
1
1
1
...

result:

ok 50014 lines

Test #81:

score: 0
Accepted
time: 564ms
memory: 9092kb

input:

50000 49999
45895 3922 30361418
21874 14474 104392820
39626 34823 83430888
5189 6472 8200216
36193 1872 35020678
26063 7150 130732294
18760 28835 51239548
32874 21952 2644170
1122 49427 10705266
41696 3543 2533765
7963 500 138055955
16249 41532 167525357
26431 19428 109064387
34698 31060 153448620
2...

output:

1
5
3
1
1
3
1
1
55
1
1
1
1
1
82
1
1
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
39
1
1
1
8
1
1
1
1
1
1
191
1
1
10
2
1
1
1
194
1
1
1
3
1
1
1
1
1
1
1
1
1
1
2
1
1
1
1
1
1
3
2
2
1
1
1
1
1
1
1
1
1
6
1
1
1
1
1
24
1
1
4
5
2
1
1
1
1
1
1
1
3
43
6
1
19
1
1
1
1
1
1
1
1
4
4
1
1
1
10
1
1
1
13
1
1
26
1
1
1
1
1
2
5
1
1
1
1
16
1...

result:

ok 89915 lines

Test #82:

score: 0
Accepted
time: 560ms
memory: 9064kb

input:

50000 49999
35341 13520 75189991
26545 49269 49720500
16246 22640 109063178
35433 46589 160669811
5786 1083 246966388
4466 48857 38043514
11816 6000 149655265
3107 31468 92981554
19886 14823 58818510
48925 7887 39848603
32929 10764 46941811
27178 8517 388330335
26641 43632 49423087
35866 38748 26353...

output:

1
1
1
1
33
1
1
1
1
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
2
1
1
1
1
1
1
5
1
4
8
1
1
1
164
1
3
1
1
1
1
11
4
1
7
1
1
2
1
1
1
1
1
1
1
1
1
1
1
17
1
1
1
14
1
1
1
1
1
1
4
1
1
1
1
1
1
1
1
1
1
1
5
31
1
15
1
1
1
3
1
1
6
1
1
1
1
3
1
1
1
1
1
1
3
52
1
1
5
1
1
1
12
1
129
1
1
1768
1
1
1
1
1
1
1
1
4
1
1
2
3
1
1
1
1
4
1
1...

result:

ok 89915 lines

Test #83:

score: 0
Accepted
time: 554ms
memory: 8928kb

input:

50000 49999
25529 24861 141472529
32875 12248 104392820
15921 39212 305653110
28320 39686 119311327
35421 694 35020678
14424 5372 130732294
1812 36451 273461770
6965 15454 2644170
4884 14172 10705266
35538 26406 2533765
22100 30598 138055955
14130 47258 167525357
17570 17146 109064387
22098 17556 15...

output:

1
1
4
1
1
1
1
1
84
1
1
1
1
1
139
1
1
1
1
1
1
2
1
1
1
1
1
33
1
1
1
1
56
1
1
1
14
1
1
1
1
1
1
308
1
1
5
1
1
1
3
188
1
1
1
1
1
1
1
1
1
1
1
1
1
1
5
1
1
1
1
1
1
1
1
13
1
1
3
1
57
1
15
8
17
2
1
1
1
1
12
14
1
5
2
7
3
1
1
2
1
2
1
1
1
29
5
1
1
1
1
2
1
4
1
1
1
6
4
1
1
1
4
1
2
1
3
1
1
30
1
1
1
1
2
1
1
1
1
1
1
...

result:

ok 89915 lines

Test #84:

score: 0
Accepted
time: 1907ms
memory: 11024kb

input:

50000 49999
45895 3922 328676792
21874 14474 164151658
39626 34823 110423795
5189 6472 309826180
36193 1872 41504476
26063 7150 265344632
18760 28835 3767059
32874 21952 45068961
1122 49427 136598663
41696 3543 185438
7963 500 59485429
16249 41532 161817297
26431 19428 78346162
34698 31060 74148359
...

output:

1
1
1
1
1
1
1
1
1
1
15
1
1
1
1
1
1
14
15
1
7
2
1
1
1
61
1
1
15
1
1
1
25
2
5
6
1
7
1
1
33
1
3
2
1
1
1
1
1
1
1
28
12
1
1
49
1
1
1
11
1
1
2
8
1
1
1
1
1
1
1
5
2
4
1
20
7
2
1
1
2
1
2
1
1
1
1
1
1
9
1
2
1
1
1
1
1
1
1
1
1
1
27
1
3
1
1
2
1
5
1
1
1
1
1
3
2
1
1
1
7
1
5
16
1
1
1
1
1
6
1
1
1
1
14
1
1
1
4
10
1
1
...

result:

ok 10049 lines

Test #85:

score: 0
Accepted
time: 1871ms
memory: 11024kb

input:

50000 49999
35341 13520 44501821
26545 49269 57371778
16246 22640 8148124
35433 46589 84398518
5786 1083 118590011
4466 48857 57675455
11816 6000 180842678
3107 31468 80673773
19886 14823 23138841
48925 7887 67737102
32929 10764 199468875
27178 8517 45842433
26641 43632 17024200
35866 38748 18946241...

output:

1
2
1
1
1
1
8
1
4
16
1
3
1
1
1
1
1
1
1
1
3
1
1
1
1
2
10
10
1
1
1
1
3
8
13
1
2
1
1
1
1
1
6
1
4
1
1
1
1
1
4
1
1
1
1
1
1
1
1
1
1
1
1
1
49
1
1
1
2
1
1
1
1
1
1
1
1
104
1
1
79
1
2
1
5
1
1
1
1
1
13
5
1
1
1
1
1
1
1
5
1
1
1
1
1
3
1
2
1
1
1
2
1
1
1
46
3
1
1
1
1
1
24
16
2
1
1
41
1
1
1
6
1
2
7
1
1
18
1
23
1
155...

result:

ok 10049 lines

Test #86:

score: 0
Accepted
time: 1973ms
memory: 11064kb

input:

50000 49999
25529 24861 217565681
32875 12248 53040547
15921 39212 443757128
28320 39686 87603958
35421 694 41504476
14424 5372 154233521
1812 36451 448211503
6965 15454 45068961
4884 14172 136598663
35538 26406 185438
22100 30598 59485429
14130 47258 272928408
17570 17146 78346162
22098 17556 74148...

output:

1
2
1
1
1
1
16
1
1
1
12
3
1
1
1
1
1
13
7
1
2
3
1
1
1
36
1
1
25
15
1
1
41
1
1
1
1
9
1
1
3
1
1
4
1
1
1
1
1
1
1
86
4
1
1
73
1
1
1
51
1
1
1
133
1
2
1
1
1
1
1
2
7
1
1
4
29
20
1
1
11
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
1
1
1
1
9
1
1
1
5
1
1
1
1
1
9
1
1
7
32
1
1
1
11
1
3
144
1
1
2
1
6
4
1
1
2
1
1
1
1
1
2
24
...

result:

ok 10049 lines

Subtask #6:

score: 0
Skipped

Dependency #1:

0%