QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#396010#185. Bridgeszjs100 ✓672ms9044kbC++173.4kb2024-04-22 09:38:052024-04-22 09:38:06

Judging History

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

  • [2024-04-22 09:38:06]
  • 评测
  • 测评结果:100
  • 用时:672ms
  • 内存:9044kb
  • [2024-04-22 09:38:05]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

class dsu_rollback {
  vector<int> ps;  // parent or size
  vector<pair<int, int>> record;
  int ecnt = 0;  // number of edges added.

 public:
  dsu_rollback(int n) : ps(n, -1), record(n - 1) {}
  void clear() {
    fill(ps.begin(), ps.end(), -1);
    ecnt = 0;
  }
  int root(int u) const {
    while (ps[u] >= 0) u = ps[u];
    return u;
  }
  int size(int u) const { return -ps[root(u)]; }
  int edge_cnt() const { return ecnt; }
  bool merge(int u, int v) {
    u = root(u);
    v = root(v);
    if (u == v) return 0;
    if (ps[u] < ps[v]) swap(u, v);
    ps[v] += ps[u];
    record[ecnt++] = {u, ps[u]};
    ps[u] = v;
    return 1;
  }
  void rollback() {
    assert(ecnt > 0);
    auto [u, sz] = record[--ecnt];
    int v = ps[u];
    ps[u] = sz;
    ps[v] -= sz;
  }
  void rollback_to(int edge_cnt) {
    while (ecnt > edge_cnt) rollback();
  }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<int> u(m), v(m), d(m);
  auto comp = [&](int i, int j) { return d[i] > d[j]; };
  for (int i = 0; i < m; i++) {
    cin >> u[i] >> v[i] >> d[i];
    u[i]--;
    v[i]--;
  }
  vector<int> sorted_edges(m);
  iota(sorted_edges.begin(), sorted_edges.end(), 0);
  sort(sorted_edges.begin(), sorted_edges.end(), comp);
  int q;
  cin >> q;
  vector<int> t(q), a(q), b(q), ans(q);
  auto comp2 = [&](int i, int j) { return b[i] > b[j]; };
  dsu_rollback dsu(n);
  vector<int> e(m);  //用于归并排序

  const int B = max(1., sqrt(log2(n) * m));

  vector<int> changed(m);
  vector<int> real_d(m);

  for (int i = 0; i < q;) {
    vector<int> queries;
    int beg = i;
    int end = min(q, i + B);

    for (; i < end; i++) {
      cin >> t[i] >> a[i] >> b[i];
      if (t[i] == 1) {
        a[i]--;
        changed[a[i]] = 1;
      } else {
        queries.push_back(i);
        a[i]--;
      }
    }

    vector<int> changed_edges, unchanged_edges;
    for (int eid: sorted_edges) // eid: edge id
      if (changed[eid])
        changed_edges.push_back(eid);
      else
        unchanged_edges.push_back(eid);

    sort(queries.begin(), queries.end(), comp2);

    auto it = unchanged_edges.begin();

    for (int id: queries) {
      for (; it != unchanged_edges.end() && d[*it] >= b[id]; it++) {
        dsu.merge(u[*it], v[*it]);
      }

      // 对于每条在当前块内被修改过的边,计算它在当前询问时的权值。
      // real_d[j]:第j条边在当前询问时的权值。
      for (int j: changed_edges)
        real_d[j] = d[j];

      for (int j = beg; j < id; j++) {
        if (t[j] == 1)
          real_d[a[j]] = b[j];
      }

      int edge_cnt = dsu.edge_cnt();
      for (int j: changed_edges)
        if (real_d[j] >= b[id]) dsu.merge(u[j], v[j]);

      ans[id] = dsu.size(a[id]);

      dsu.rollback_to(edge_cnt);
    }

    for (int j = beg; j < end; j++)
      if (t[j] == 1)
        d[a[j]] = b[j];

    sort(changed_edges.begin(), changed_edges.end(), comp);
    // 归并
    merge(unchanged_edges.begin(),
          unchanged_edges.end(),
          changed_edges.begin(),
          changed_edges.end(),
          sorted_edges.begin(),
          comp);

    dsu.clear();
    for (int j: changed_edges)
      changed[j] = 0;
  }

  for (int i = 0; i < q; i++) {
    if (t[i] == 2)
      cout << ans[i] << '\n';
  }
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 13
Accepted

Test #1:

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

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: 3732kb

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: 3616kb

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: 0
Accepted
time: 0ms
memory: 3652kb

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
5
5

result:

ok 5 lines

Test #5:

score: 0
Accepted
time: 7ms
memory: 3824kb

input:

100 1000
26 42 977322268
4 29 374382133
1 19 717262653
80 56 835233390
58 54 591443635
63 6 579687470
85 81 118110131
33 100 533388119
24 46 591205239
94 32 637495476
60 93 638216409
55 7 413175730
38 43 414269997
48 30 773236579
67 27 441100383
44 36 784705206
28 56 300064078
13 60 490548719
94 19 ...

output:

100
100
100
100
100
100
100
100
17
100
100
100
100
100
5
100
98
100
100
100
100
100
100
100
100
100
100
100
100
96
100
2
42
100
100
100
86
97
100
100
100
98
100
100
100
100
100
97
100
100
100
100
100
100
100
100
100
100
100
100
100
98
100
100
100
100
100
5
100
100
100
100
100
98
100
100
100
100
1
10...

result:

ok 4938 lines

Test #6:

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

input:

1 0
10000
2 1 198824732
2 1 485321921
2 1 632483476
2 1 51814372
2 1 599796663
2 1 786502474
2 1 231528808
2 1 911511073
2 1 372581312
2 1 168699670
2 1 155928174
2 1 636544973
2 1 221309003
2 1 934838177
2 1 927074369
2 1 66460573
2 1 854380894
2 1 763039163
2 1 203254324
2 1 525763932
2 1 58538356...

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 10000 lines

Test #7:

score: 0
Accepted
time: 4ms
memory: 3848kb

input:

14 91
14 9 741787656
13 11 380113631
4 1 156765724
5 10 110432834
3 2 1
5 8 39463185
6 7 725978322
13 4 785136504
8 11 446396092
2 1 949863738
10 9 808326751
3 14 623625192
13 1 73346434
4 3 319943247
10 11 874189144
6 5 177923890
14 11 892698206
10 8 602358072
10 12 7684455
14 8 228264999
12 2 8612...

output:

14
14
14
14
1
2
10
14
14
14
1
14
10
14
14
14
14
14
14
14
14
14
14
14
14
14
14
14
14
14
1
14
14
12
14
1
14
14
14
14
1
14
2
14
14
14
14
14
14
14
14
14
14
13
14
14
14
14
14
14
14
1
14
14
14
2
14
14
14
14
14
14
14
3
14
14
14
14
14
14
14
1
14
14
2
14
14
14
14
14
14
14
14
14
14
14
14
1
14
14
14
14
14
1
14...

result:

ok 5047 lines

Test #8:

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

input:

14 91
14 9 811041661
13 11 347161250
4 1 1000000000
5 10 1000000000
3 2 190616738
5 8 1000000000
6 7 1000000000
13 4 839799889
8 11 1000000000
2 1 1000000000
10 9 925475672
3 14 327778434
13 1 709412306
4 3 696232213
10 11 1000000000
6 5 1000000000
14 11 994412543
10 8 1000000000
10 12 1000000000
14...

output:

10
10
10
10
10
10
14
10
10
14
14
10
10
14
10
14
14
10
10
10
10
10
14
14
13
10
10
10
10
10
14
10
10
10
10
10
10
14
10
10
10
14
10
10
10
10
10
10
10
10
14
10
10
14
10
1
10
13
14
14
14
10
10
10
10
10
10
10
10
10
14
10
10
10
10
14
10
10
10
10
10
10
10
10
10
10
14
10
10
10
10
10
10
14
14
14
10
10
14
14
1...

result:

ok 5085 lines

Test #9:

score: 0
Accepted
time: 4ms
memory: 3888kb

input:

100 100
74 34 685914765
44 9 1
41 36 6
49 22 1
40 84 1
7 40 1
57 31 264482875
16 87 3
66 10 3
68 7 2
92 43 2
33 57 736695588
42 23 2
64 45 1
85 81 4
43 84 1
62 91 2
13 49 2
95 50 1
76 54 1
49 88 1
37 73 2
48 60 1
65 85 3
69 62 2
60 26 1
15 12 1
82 51 2
100 25 3
21 78 1
59 52 1
10 49 2
80 60 2
89 8 3...

output:

84
15
84
84
84
84
84
84
1
84
5
1
84
3
3
1
1
1
1
84
10
84
7
1
84
1
84
1
1
4
84
3
19
1
15
84
84
84
1
84
84
84
84
2
1
84
4
1
2
84
1
84
84
84
2
2
84
84
1
2
84
3
1
5
1
1
4
1
1
84
84
3
20
84
4
6
84
9
4
1
84
1
1
1
84
84
84
84
84
1
84
21
5
2
2
1
1
84
4
84
84
84
5
1
4
6
84
21
1
21
84
84
84
2
84
1
1
1
84
1
84...

result:

ok 4993 lines

Test #10:

score: 0
Accepted
time: 4ms
memory: 4044kb

input:

100 100
74 34 1000000000
44 9 715200993
41 36 904630372
49 22 962500864
40 84 729454076
7 40 377495011
57 31 1000000000
16 87 325040395
66 10 52188391
68 7 212790030
92 43 78499164
33 57 1000000000
42 23 501453286
64 45 269034829
85 81 219465148
43 84 451775169
62 91 579206993
13 49 553447314
95 50 ...

output:

1
60
5
2
24
22
2
1
1
4
40
1
77
72
1
4
1
38
1
2
42
1
3
1
76
1
1
1
2
51
1
28
74
1
38
80
76
1
1
69
3
83
1
5
5
5
83
68
5
2
1
1
1
81
5
2
1
4
1
2
5
52
1
5
78
1
51
2
5
71
2
66
1
84
2
36
1
8
3
1
1
1
78
1
68
81
16
76
2
84
84
2
5
1
63
2
1
63
1
1
74
76
5
1
5
3
1
1
1
1
3
1
1
3
2
5
1
2
24
5
1
1
21
1
1
81
21
4
3
...

result:

ok 4993 lines

Test #11:

score: 0
Accepted
time: 4ms
memory: 3900kb

input:

100 100
74 34 228801803
44 9 1
41 36 4
49 22 1
40 84 4
7 40 3
57 31 704030998
16 87 4
66 10 1
68 7 7
92 43 1
33 57 728028523
42 23 1
64 45 3
85 81 4
43 84 3
62 91 3
13 49 1
95 50 1
76 54 1
49 88 1
37 73 3
48 60 4
65 85 1
69 62 1
60 26 4
15 12 3
82 51 4
100 25 1
21 78 4
59 52 3
10 49 1
80 60 2
89 8 6...

output:

5
84
84
84
84
84
1
84
84
84
84
84
1
84
84
84
84
1
84
84
1
1
84
1
84
1
84
84
84
84
84
84
84
84
84
84
84
84
84
84
1
84
84
84
84
84
84
84
84
84
84
84
84
84
84
84
1
84
84
84
1
84
84
84
1
84
84
84
84
84
84
84
84
84
1
84
84
84
84
5
84
84
84
84
84
84
84
84
84
84
84
84
84
84
84
84
84
84
84
84
84
84
84
84
84...

result:

ok 4976 lines

Test #12:

score: 0
Accepted
time: 4ms
memory: 3904kb

input:

100 100
75 55 18370417
87 15 24759751
35 90 180232308
93 13 4822137
52 63 94962544
47 83 518290304
79 21 1829303
7 97 537385812
75 19 52188390
25 8 212790030
87 43 24037796
44 94 324191076
9 92 333255997
54 51 12968272
34 6 253267674
95 64 20519430
31 58 28891962
12 23 575634244
50 4 110619991
33 9 ...

output:

3
1
82
100
1
2
100
1
1
1
2
22
6
3
10
3
16
10
22
2
1
1
4
1
2
8
3
5
7
1
32
1
6
12
8
2
6
3
6
3
1
55
100
1
4
2
5
4
1
1
2
13
75
3
1
55
6
2
3
1
9
1
13
1
9
60
3
1
1
100
1
1
1
100
15
1
3
3
75
6
100
12
15
1
2
3
8
1
8
15
6
1
3
1
1
14
4
1
1
3
8
2
1
12
24
4
2
1
30
3
100
1
1
1
4
24
1
6
1
1
15
4
30
1
13
1
3
1
3
7...

result:

ok 4993 lines

Test #13:

score: 0
Accepted
time: 4ms
memory: 3852kb

input:

100 100
75 55 827381885
87 15 189426033
35 90 314088225
93 13 962500864
52 63 771307313
47 83 930460632
79 21 691878465
7 97 859582759
75 19 557403081
25 8 989321957
87 43 217067250
44 94 805985038
9 92 924454229
54 51 269034829
34 6 811380927
95 64 180328209
31 58 436656654
12 23 947277637
50 4 917...

output:

5
8
1
7
1
7
6
48
11
3
1
13
2
5
1
60
1
1
13
1
2
45
2
1
2
1
5
13
1
4
3
1
4
52
52
4
31
1
52
4
1
1
2
1
2
1
2
1
3
24
60
2
8
1
14
2
1
2
3
2
7
1
8
4
8
2
100
2
4
19
2
1
8
100
1
4
2
90
17
1
2
48
2
48
1
3
4
3
17
1
3
2
2
2
3
1
4
2
1
1
1
3
1
44
3
5
1
90
1
16
5
14
1
3
2
1
5
63
3
5
1
3
1
42
2
14
5
1
1
1
2
1
4
1
3...

result:

ok 4993 lines

Test #14:

score: 0
Accepted
time: 4ms
memory: 4108kb

input:

100 100
75 55 523280580
87 15 97273903
35 90 24566276
93 13 66762694
52 63 62457076
47 83 14559451
79 21 198058038
7 97 303933384
75 19 357282957
25 8 15676722
87 43 20498361
44 94 361533141
9 92 479521475
54 51 188367392
34 6 351945785
95 64 31785315
31 58 12985500
12 23 63507527
50 4 25758008
33 9...

output:

1
1
5
13
9
1
11
4
7
25
2
13
15
1
13
66
33
3
13
5
1
2
1
1
4
11
13
9
4
1
3
9
16
7
11
1
7
11
28
5
11
13
9
9
13
2
5
10
9
15
4
24
3
3
9
62
15
3
9
1
14
17
1
13
1
17
9
4
1
1
15
11
2
9
9
1
10
4
1
3
9
2
13
1
4
9
9
5
65
1
62
13
13
11
11
1
6
1
1
1
6
8
99
7
3
1
3
1
5
32
1
1
9
3
18
6
4
65
10
66
1
9
3
2
4
10
4
65...

result:

ok 4952 lines

Test #15:

score: 0
Accepted
time: 5ms
memory: 3900kb

input:

100 150
72 39 459437566
99 33 240975967
60 42 71297038
100 66 81817608
7 97 40586687
94 44 488433191
9 33 155257410
38 59 258106533
34 6 7722722
97 89 212790030
73 34 78499164
83 88 261128013
39 98 335913783
20 81 140652810
14 30 129337570
83 47 56555466
18 2 676617230
37 42 79132016
80 35 633142513...

output:

1
1
11
1
1
3
6
41
4
1
25
2
5
5
2
46
45
2
23
34
34
26
11
26
1
6
23
1
100
5
100
2
1
5
30
6
4
61
62
26
5
26
100
26
100
2
1
5
3
1
66
27
26
26
100
3
26
16
24
26
26
18
1
7
1
3
34
67
1
7
5
30
100
4
3
18
27
18
1
3
3
71
19
66
7
24
39
9
26
98
39
100
1
42
38
5
11
100
42
26
1
37
1
27
100
40
42
37
5
37
37
58
40
...

result:

ok 5046 lines

Test #16:

score: 0
Accepted
time: 5ms
memory: 4040kb

input:

100 150
72 39 950686765
99 33 716054509
60 42 836724016
100 66 497108440
7 97 168321467
94 44 992895576
9 33 938438676
38 59 548639568
34 6 773535187
97 89 982737825
73 34 894334764
83 88 687830748
39 98 950242721
20 81 613284326
14 30 602412784
83 47 673179224
18 2 917339878
37 42 581986238
80 35 9...

output:

1
4
3
3
22
1
2
22
2
3
1
4
20
1
1
58
22
30
3
1
2
1
8
1
16
4
3
22
1
46
2
2
16
3
1
1
14
5
1
1
8
2
1
1
100
5
16
1
1
6
3
1
1
1
100
4
100
14
27
45
1
2
1
10
1
4
31
100
1
3
1
1
2
1
1
1
17
2
50
24
2
1
40
54
1
2
2
4
4
1
1
1
4
31
1
1
1
1
4
100
8
11
7
22
2
2
16
1
4
1
2
1
4
1
13
5
18
1
99
1
10
25
100
1
10
3
18
9...

result:

ok 5046 lines

Test #17:

score: 0
Accepted
time: 5ms
memory: 3776kb

input:

100 150
72 39 23280580
99 33 97273903
60 42 24566276
100 66 254262694
7 97 437457076
94 44 139559451
9 33 10558038
38 59 241433384
34 6 107282957
97 89 140676722
73 34 20498361
83 88 111533141
39 98 604521475
20 81 188367392
14 30 226945785
83 47 94285315
18 2 512985500
37 42 313507527
80 35 1507580...

output:

61
1
22
3
18
14
19
1
19
5
1
1
37
1
100
30
72
18
98
99
1
1
1
100
3
30
17
23
18
1
18
18
1
100
2
8
2
30
18
8
29
1
1
45
100
1
28
1
24
6
1
1
100
1
2
15
1
69
9
30
1
17
29
69
1
99
20
11
99
99
6
1
6
29
1
23
99
11
1
29
9
3
3
1
18
22
22
42
4
28
29
1
2
1
98
3
29
1
1
29
18
99
1
19
1
41
29
8
97
1
16
8
68
3
8
8
1...

result:

ok 5078 lines

Test #18:

score: 0
Accepted
time: 4ms
memory: 3888kb

input:

100 100
92 90 2
13 45 2
64 25 1
56 84 1
65 57 1
95 8 1
69 40 2
19 62 1
93 82 1
69 86 1
13 95 2
32 36 1
30 69 2
28 85 2
61 19 2
16 95 1
18 75 2
99 24 2
75 54 2
94 17 1
5 4 1
77 43 2
46 97 2
20 2 1
61 53 2
92 73 1
27 43 1
10 41 1
39 13 2
58 37 1
57 70 1
4 18 1
14 69 1
75 52 2
38 50 1
50 97 1
81 10 2
1...

output:

10
2
1
80
2
80
3
1
3
80
80
80
80
3
2
1
80
1
80
80
1
4
80
80
12
80
12
80
1
80
3
12
12
80
80
80
1
2
80
80
4
1
80
1
1
1
2
80
1
80
2
1
1
1
17
1
1
80
80
3
1
80
1
80
80
80
1
1
5
80
11
2
80
80
80
1
2
80
1
1
2
4
80
1
2
11
4
80
18
80
18
1
4
80
1
2
80
80
1
80
80
6
80
1
1
6
7
2
6
16
80
4
80
1
2
1
2
80
1
80
16
...

result:

ok 4949 lines

Test #19:

score: 0
Accepted
time: 4ms
memory: 3900kb

input:

100 100
20 34 3
91 98 2
40 13 1
34 24 1
55 90 3
12 23 1
87 80 3
96 71 1
50 98 2
26 3 1
32 66 1
64 45 3
60 44 3
42 77 3
54 78 2
99 2 2
36 46 1
51 10 2
67 96 2
15 60 1
8 25 3
51 78 1
19 20 3
54 59 3
72 68 1
22 29 1
80 51 2
54 68 1
70 77 1
9 91 2
41 64 2
17 22 3
5 91 2
58 39 1
66 15 2
8 6 3
66 80 3
71 ...

output:

10
1
5
81
81
4
52
1
81
1
1
1
81
2
1
50
1
57
1
2
1
2
81
1
5
1
16
16
3
1
1
1
2
2
81
81
3
1
81
2
1
2
81
4
1
81
3
1
1
81
81
30
2
81
30
81
1
81
30
1
1
81
81
3
2
1
32
4
1
1
1
1
81
81
3
1
4
2
1
81
1
48
6
4
1
81
81
1
81
1
4
81
1
81
6
1
1
3
81
1
52
81
1
52
81
5
81
81
1
81
6
5
2
81
1
2
1
9
4
1
1
81
1
1
4
40
1...

result:

ok 5065 lines

Subtask #2:

score: 16
Accepted

Test #20:

score: 16
Accepted
time: 348ms
memory: 7232kb

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: 356ms
memory: 7356kb

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: 365ms
memory: 7208kb

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: 374ms
memory: 7376kb

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: 371ms
memory: 7412kb

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: 388ms
memory: 7180kb

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: 395ms
memory: 7228kb

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: 377ms
memory: 7360kb

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: 19ms
memory: 4820kb

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: 322ms
memory: 7312kb

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: 289ms
memory: 7364kb

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: 248ms
memory: 7396kb

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: 216ms
memory: 7284kb

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: 291ms
memory: 6496kb

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: 146ms
memory: 5140kb

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: 301ms
memory: 6492kb

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: 289ms
memory: 6480kb

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: 14ms
memory: 4648kb

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: 296ms
memory: 6324kb

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: 260ms
memory: 6448kb

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: 241ms
memory: 6504kb

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: 168ms
memory: 6408kb

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: 165ms
memory: 6384kb

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: 181ms
memory: 6396kb

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: 175ms
memory: 6460kb

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: 14
Accepted

Test #45:

score: 14
Accepted
time: 303ms
memory: 8876kb

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:

2
2
1
48165
37106
1
48830
1
47126
3
37777
1
14
1
1
24
1
48755
44817
17617
24322
48909
7
47708
1
41147
48949
45939
48022
1
26304
1
1
22363
24527
46076
37978
1
1
2
44508
1
47625
48554
1
2
4
48711
48431
41315
2
2
9364
3
37323
46978
39881
32373
5
39140
47126
44635
47960
1
48141
47192
28
27190
38467
4
48...

result:

ok 100000 lines

Test #46:

score: 0
Accepted
time: 19ms
memory: 4820kb

input:

1 0
100000
2 1 449565301
2 1 418018081
2 1 566914037
2 1 386096903
2 1 325815043
2 1 515513392
2 1 349622300
2 1 5042450
2 1 469351640
2 1 219472495
2 1 510850771
2 1 885705436
2 1 594457820
2 1 410756749
2 1 959667810
2 1 479458147
2 1 705147675
2 1 140732217
2 1 281668854
2 1 333164650
2 1 3934393...

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 #47:

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

input:

447 99681
432 259 741787656
82 143 380113631
317 104 156765724
76 270 110432834
212 261 207353276
25 300 39463185
14 56 725978322
155 236 785136504
398 265 446396092
343 1 949863738
1 110 808326751
97 180 623625192
308 92 73346434
253 252 319943247
362 372 874189144
206 402 177923890
22 205 89269820...

output:

447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
446
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
272
447
...

result:

ok 10000 lines

Test #48:

score: 0
Accepted
time: 40ms
memory: 7040kb

input:

447 99681
432 259 1000000000
82 143 1000000000
317 104 1000000000
76 270 1000000000
212 261 1000000000
25 300 1000000000
14 56 1000000000
155 236 1000000000
398 265 1000000000
343 1 1000000000
1 110 1000000000
97 180 1000000000
308 92 1000000000
253 252 1000000000
362 372 1000000000
206 402 10000000...

output:

443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
...

result:

ok 10000 lines

Test #49:

score: 0
Accepted
time: 264ms
memory: 9004kb

input:

50000 100000
36430 26409 3
14637 42323 4
4352 35569 1
14530 43949 2
22805 22365 1
49910 3378 4
1494 5088 2
18398 11098 5
14316 10284 5
11863 11681 2
29896 36912 3
30517 45099 4
36259 16961 1
40065 27965 2
2717 46870 3
34358 5004 1
3460 37101 2
13920 793 1
23824 38760 2
47941 20057 1
25012 1567 2
377...

output:

2
48980
48980
48980
2
48980
46861
46861
2
46861
39197
1
39197
46861
48980
2
18
1
48980
39197
48980
39197
39197
46861
8
48980
39197
46861
13013
39197
46861
39197
48980
48980
39197
39197
48980
48980
39197
39197
1
4
46861
48980
1
46861
46861
1
1
48980
78
13013
39197
46861
48980
46861
5
46861
39197
1
2
...

result:

ok 100000 lines

Test #50:

score: 0
Accepted
time: 293ms
memory: 8952kb

input:

50000 100000
36430 26409 891600895
14637 42323 146361404
4352 35569 221787293
14530 43949 358568724
22805 22365 190650305
49910 3378 414088144
1494 5088 592528192
18398 11098 542270793
14316 10284 350034541
11863 11681 878653236
29896 36912 168210793
30517 45099 365684348
36259 16961 960673881
40065...

output:

1
48294
4
20863
1
43446
48305
48732
46205
44911
48772
48525
21
44625
42513
48262
22234
46164
1
1
1
41815
1
44908
3
42859
47778
27167
48693
1
43420
2
47449
1
3
1
48843
2
1
47884
2
5
41904
1
42400
46059
4
2
1
30131
42694
11231
1
1
48952
1
37568
40717
1
44503
1
46559
1
47010
39169
42073
42791
1
1
26772...

result:

ok 100000 lines

Test #51:

score: 0
Accepted
time: 255ms
memory: 8780kb

input:

50000 100000
36430 26409 3
14637 42323 1
4352 35569 3
14530 43949 3
22805 22365 3
49910 3378 4
1494 5088 3
18398 11098 4
14316 10284 6
11863 11681 1
29896 36912 1
30517 45099 6
36259 16961 1
40065 27965 1
2717 46870 1
34358 5004 2
3460 37101 2
13920 793 1
23824 38760 3
47941 20057 2
25012 1567 4
377...

output:

39450
11923
39450
48980
46957
11923
39450
46957
48980
48980
1
1
46957
39450
39450
48980
46957
98
46957
48980
48980
48980
1
48980
48980
39450
39450
46957
46957
46957
11923
46957
48980
4
1
48980
48980
46957
1
1
11923
48980
46957
48980
48980
48980
48980
39450
48980
1
11923
48980
1
39450
46957
1
11923
3...

result:

ok 100000 lines

Test #52:

score: 0
Accepted
time: 165ms
memory: 7288kb

input:

50000 50000
3018 2466 31856784
44110 19797 43049494
29377 21015 99965770
18756 28173 453546998
30313 33813 132485681
29934 42387 8136444
24167 31408 174713487
21584 31531 8206037
37467 45599 1224360
19205 26080 254678499
3769 35418 112134933
8806 44621 74762896
15381 26395 186780991
30397 3214 31302...

output:

37
21
1
1
5
8
66
19
3
3
17
2
3
1
8
15
2
1
3
2
146
11
47
3
1
2
2
3
8
3
7
3
1
27
4
1
1
2
4
1
1
1
2
4
1
3
1
3
1
2
2
1
1
4
3
2
3
1
2
139
6
2
1
1
4
1
1
6
1
5
2
26
1
1
1
81
1
1
3
1
2
2
4
1
414
4
14
1
1
7
1
1
2
1
4
15
4
15
1
1
1
2774
9
8
3
4
35
5
3
4
6
2
9
4
1
1
1
50
35
115
2
33
7
3
3
1
2
1
1
138
2
3
3
15
...

result:

ok 100000 lines

Test #53:

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

input:

50000 50000
3018 2466 986978263
44110 19797 568890536
29377 21015 499670939
18756 28173 839504998
30313 33813 296515410
29934 42387 607104763
24167 31408 819593187
21584 31531 932588647
37467 45599 781307391
19205 26080 840849964
3769 35418 172098007
8806 44621 514674542
15381 26395 631793541
30397 ...

output:

2
5
7
2
10
1
4
2
3
1
2
1
1
1
1
2
1
1
11
1
1
39
8
6
1
11
4
1
1
3
1
3
5
1
2
9
1
2
2
18
17
2
1
1
2
1
1
1
3
2
12
2
8
8
3
9
10
15
1
10
75
1
2
29
1
2
1
402
78
1
17
2
1
6
13
2
3
11
1
2
2
2
4
1
2
5
3
2
4
2
4
3
3
1
1
1
2
3
1
1
1
3
3
4
10
1
1
9
21
1
1
4
12
4
11
2
1
1
2
4
1
2
1
3
9
2
25
3
6
3
2
12
1704
2
3
4
2...

result:

ok 100000 lines

Test #54:

score: 0
Accepted
time: 166ms
memory: 7316kb

input:

50000 50000
3018 2466 79153577
44110 19797 74388894
29377 21015 68432062
18756 28173 253920608
30313 33813 96749945
29934 42387 211811490
24167 31408 260503273
21584 31531 6623362
37467 45599 10982747
19205 26080 299300783
3769 35418 193906707
8806 44621 101185330
15381 26395 375628184
30397 3214 30...

output:

17
106
67
624
499
2727
182
556
365
801
128
3016
835
25
429
79
301
1186
23
189
10
2
362
17
147
896
88
125
176
77
536
429
352
348
61
98
1061
94
499
2229
79
143
440
16
14
47
40
53
374
215
22
89
2858
55
379
756
218
268
17
191
13
5
1359
232
46
247
105
918
105
1442
243
6
52
1246
17
449
560
115
37
37
57
65...

result:

ok 100000 lines

Test #55:

score: 0
Accepted
time: 256ms
memory: 8200kb

input:

50000 75000
33889 6094 187797790
6038 24958 249870404
39193 12649 47857772
404 6521 64489103
45477 33178 61611498
33350 45699 89159626
39479 5160 5857314
18313 12942 59456592
16738 45598 162999431
6188 46675 375553080
5923 47352 267640
18352 44726 24162741
25970 36584 160755499
21001 12852 115486368...

output:

1
5
6944
1
62
300
9
1
8
4
1
33
35
12
40
324
39
79
1
1
1
203
1
1
151
2
2
1156
390
1
2106
19
2
1
1
3
1
1
4
522
25
2
1
1
5
5
4
6
136
300
8
1
15
5
6781
4
1
50
64
1
6
1
2
3
17
3
67
2
1
3
4
961
7
2
42
2033
1
4
45
128
1
1
1
31
4
2
8
26
7
30
1
1
6781
1
46
63
185
1
2
1
328
11
28
491
16
14
2
156
284
63
41
1
1...

result:

ok 100000 lines

Test #56:

score: 0
Accepted
time: 230ms
memory: 8360kb

input:

50000 75000
33889 6094 420893227
6038 24958 452093259
39193 12649 817331307
404 6521 852910965
45477 33178 817357513
33350 45699 743854302
39479 5160 973119288
18313 12942 823671581
16738 45598 734695190
6188 46675 440713089
5923 47352 358615002
18352 44726 690405567
25970 36584 376493341
21001 1285...

output:

1
8
1
5
9
1
478
6
4
43
8
88
5
2
1
2
6
12
13
17
2
1
4
2
630
2
39
7
5
58
2
1
382
2822
6
1
11
1506
48
8
7
3
10
3
1
38
1
7
4
2
1
364
3
488
16
60
10
1
9
2
11
23
19
6
1
12
20
1
54
1
3
158
5
2473
1
1
834
1
29
1
1
23
4
361
1247
414
1
4
2
80
2
67
1
1
4
1
258
16
2
82
4
3
18
67
76
5046
138
7
1
18
2
1
8
2
1
1
1...

result:

ok 100000 lines

Test #57:

score: 0
Accepted
time: 262ms
memory: 8284kb

input:

50000 75000
33889 6094 312238223
6038 24958 105159308
39193 12649 70014492
404 6521 268819182
45477 33178 30294724
33350 45699 23408487
39479 5160 170044358
18313 12942 462115817
16738 45598 12945966
6188 46675 50759466
5923 47352 10756786
18352 44726 445834887
25970 36584 110254109
21001 12852 1876...

output:

1960
5423
1339
372
4065
5678
3450
3878
3296
2348
2416
2056
3398
2913
11761
2721
18563
5
2913
2905
3752
1974
13388
5423
3076
1689
1974
614
5423
3450
3449
3878
123
5423
48
18563
14
1177
6
1603
19
2146
1339
3749
443
5423
3537
2914
4065
519
2416
3449
3450
887
2720
3810
10743
5423
4262
37
102
536
1556
11...

result:

ok 100000 lines

Test #58:

score: 0
Accepted
time: 269ms
memory: 8836kb

input:

50000 100000
15902 37902 1
17114 1173 1
11644 26158 1
19786 42295 1
7375 13869 1
41274 22976 2
835 37821 2
43555 33134 1
43468 19565 1
9379 47294 1
16398 11626 2
38982 40565 2
37286 12116 1
47601 37754 2
48429 36718 1
42177 6120 1
4654 18153 2
18980 25667 2
14661 40435 2
32390 8457 1
21754 24732 1
4...

output:

48953
39613
39613
48953
48953
48953
39613
1
48953
1
39613
4
48953
48953
39613
48953
48953
39613
39613
39613
39613
48953
39613
48953
39613
48953
48953
39613
48953
48953
48953
48953
39613
39613
39613
39613
39613
39613
39613
39613
48953
39613
48953
39613
39613
48953
39613
39613
2
48953
48953
39613
3961...

result:

ok 100000 lines

Test #59:

score: 0
Accepted
time: 239ms
memory: 8952kb

input:

50000 100000
16622 4042 3
29296 26235 1
924 10146 2
6673 2735 1
7465 16111 1
39191 3402 1
31557 2062 3
41332 16451 1
40029 29774 1
1536 11606 1
9816 21897 2
15118 49569 3
22016 42191 1
37712 3855 2
22722 21172 1
3261 35636 2
38376 20812 2
5328 40248 3
33365 373 3
29011 31608 1
25458 39541 3
22685 16...

output:

1
22819
49028
45603
49028
49028
45603
45603
1
49028
45603
45603
45603
49028
49028
49028
22819
49028
22819
45603
22819
49028
2
49028
22819
45603
45603
2
1
49028
49028
49028
49028
71
49028
1
49028
49028
4
45603
45603
49028
9
22819
45603
49028
22819
22819
49028
49028
17
22819
49028
1
49028
1
45603
4560...

result:

ok 100000 lines

Test #60:

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

input:

49729 99012
34054 8341 4175351
18682 17977 31563632
19269 15971 316486513
16453 23315 222200372
48031 37963 328549397
35957 4042 144188344
41481 23139 199796339
30840 7454 2956883
9107 36464 105802625
15976 35553 213475524
35520 40158 41633125
27542 9944 262538992
14658 21385 146413217
27915 22932 1...

output:

162
1
152
40185
3
49369
1
43082
40012
13825
2
2
1
37937
37355
8
162
48318
1
1
40417
44848
48355
49114
81
49678
1
49166
1
47344
49715
7
5
49689
11981
46554
49369
1
48326
2326
49608
40335
3
1
10
3
6
9
44579
33623
1
49276
1
40358
1
32187
45056
178
1533
1
40012
39683
8
31113
7
23739
1153
20
7
28
49729
1...

result:

ok 100000 lines

Test #61:

score: 0
Accepted
time: 327ms
memory: 8824kb

input:

49719 98972
21767 6065 50070961
20464 17361 169248081
27314 45549 36819446
33702 41335 351272826
48558 44834 199266519
30638 21034 674557652
19478 11122 253122173
29904 49011 156855128
47670 28852 109873392
17146 14684 169743003
15703 3814 7374462
16769 39749 189412976
7203 46682 136468490
46010 203...

output:

1
1
1
2
26
147
49689
23561
41142
18
1
1
41021
49054
1
2
42761
1
10756
40184
48557
3
1
5
33981
10933
49719
1
24618
41535
1
25
54
44299
5
858
43743
21961
8665
19
27734
43186
11
23
1
34874
1
49646
1
2
48268
45
49640
48808
1
26597
2
45151
103
1
49615
1
1
1
174
13552
5
48804
48896
10
18
19
2
21753
7
2308...

result:

ok 100000 lines

Test #62:

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

input:

50000 99400
29410 30330 758567223
17803 21820 941403915
14061 46028 280515052
37193 24091 781060591
25716 20072 882860054
33445 37640 509782731
12541 23219 782716806
18523 6908 531828972
3230 32030 421168543
44552 48693 97642726
1279 2726 643181026
25106 34578 884629614
4038 37779 617488416
38071 11...

output:

49998
9
8
47672
29100
1
1
132
49992
1
7
46808
49976
49726
49996
40748
3
1
48367
6
2
1
3274
49999
992
1207
1
30090
47305
264
2
49642
1
28732
34285
49908
49963
49449
40622
1
49946
2
1
49775
49916
27
49986
85
1
39594
533
49933
1
1
32602
2
49190
49982
2
1
1
46823
3
1
48896
656
16
49594
26850
14
49952
3
...

result:

ok 100000 lines

Test #63:

score: 0
Accepted
time: 301ms
memory: 8980kb

input:

49950 99201
36281 36503 763054174
9379 38035 472773481
25806 36188 761440834
24770 43939 593827712
44117 32984 959406044
18886 41008 690486926
49627 4512 624530349
21092 16661 833081827
14094 49233 910931467
31376 2432 747917920
26336 18969 451935820
39553 16163 535086746
26124 43554 903283220
6256 ...

output:

9
49763
219
9
24398
46296
46900
1
1
1
93
5916
2
11
10
18101
49510
49887
1
382
16
49804
1
47896
1
48983
46558
17
48189
1
3151
2988
16
9151
4
46488
1
26
49529
5082
49830
16
7
13
39175
49618
1
87
2
49021
17
2
7804
22087
47920
1
19
1
46104
49549
12010
49940
1
49365
49944
3451
1
16304
48850
39516
49950
1...

result:

ok 100000 lines

Test #64:

score: 0
Accepted
time: 282ms
memory: 8588kb

input:

49998 83327
39504 32115 603170071
49865 30849 130675480
30107 3167 55412622
33018 6097 94561562
32270 43450 124904278
1328 13459 79410517
5277 31217 436853542
22995 17298 247419872
32399 25864 535304576
20487 35769 11662754
19774 21657 33814282
4158 30463 363491899
40211 40065 187002697
22211 32071 ...

output:

4987
4981
13971
16566
34472
16568
15966
34464
1391
15951
34475
15951
48451
8373
6473
49998
8622
8956
8373
8373
49998
8622
8373
15970
15992
6
4960
8622
13975
15966
16568
8956
8606
34469
8373
13975
8956
8373
34464
4960
4960
5006
15951
15966
285
4989
6446
16568
8962
988
34472
6463
15968
33095
15966
861...

result:

ok 100000 lines

Test #65:

score: 0
Accepted
time: 276ms
memory: 8512kb

input:

49992 83306
18171 44476 566111419
14354 45323 78491664
31324 42407 86408010
16269 10214 343483203
44837 22800 14793460
45715 9529 8321488
22348 19511 683659900
7036 10120 683944755
9747 12255 43970763
37546 33897 19677943
12388 12210 109434184
24731 34404 33575744
46477 2587 10649026
26986 49355 534...

output:

13375
13386
49992
9092
13500
14470
13375
13375
3112
11001
11018
4113
11002
9110
13386
13497
11001
1292
49992
13380
11002
9119
11018
3108
13289
49992
13384
13289
49992
13391
11001
1116
13384
9094
10949
3112
13375
13386
9094
821
9109
9110
9110
10999
13392
13380
13386
49992
11013
11000
22123
11001
1101...

result:

ok 100000 lines

Test #66:

score: 0
Accepted
time: 315ms
memory: 8792kb

input:

48729 95081
34569 31119 121468261
44534 42997 32387101
27645 27262 179917793
27160 40400 147086695
24917 45974 392357817
10176 23589 64525446
36132 43032 101470030
48191 26960 218513742
27615 10820 393845101
36869 33441 37211419
40354 27469 38639025
14212 10067 288238270
17744 3968 186572229
24158 3...

output:

48488
47027
46935
46745
44133
43798
47943
1
47759
48461
48565
47726
42357
5
46497
46616
48729
48729
45359
1
48723
47960
46479
48476
47710
1
46777
48729
47331
3
47730
48709
42890
44349
48596
46030
48637
42242
47498
47057
48605
48729
48157
45068
45560
9
48150
48729
48367
48729
46030
48691
48711
48709
...

result:

ok 100000 lines

Test #67:

score: 0
Accepted
time: 271ms
memory: 8368kb

input:

44729 80122
5199 20293 31
7817 41640 6
34878 22640 20
40005 33324 15
40383 32872 13
34683 29204 20
27984 14878 12
30253 38386 33
25606 20784 8
2189 25911 7
2456 33868 20
11948 9644 40
20299 36926 11
33341 21039 30
32405 33498 16
19620 43993 12
6437 37553 50
13577 29531 25
18855 28841 64
10313 6994 2...

output:

43932
43932
44630
44400
43932
44720
43932
44720
43932
44400
44630
44400
44630
44720
44400
44400
44630
44720
44720
43932
44630
44400
44720
43932
44720
44720
43932
44720
44630
44400
44630
44400
44630
43932
44630
44630
43932
44720
44400
44720
43932
44720
44400
43932
43932
44630
44400
43932
44400
1
4393...

result:

ok 100000 lines

Subtask #5:

score: 13
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #68:

score: 13
Accepted
time: 399ms
memory: 7204kb

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: 505ms
memory: 7184kb

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: 408ms
memory: 7304kb

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: 299ms
memory: 7212kb

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: 402ms
memory: 7284kb

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: 420ms
memory: 7300kb

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: 424ms
memory: 7312kb

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: 389ms
memory: 7400kb

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: 377ms
memory: 7312kb

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: 397ms
memory: 7360kb

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: 302ms
memory: 7212kb

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: 297ms
memory: 7400kb

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: 300ms
memory: 7308kb

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: 218ms
memory: 7364kb

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: 190ms
memory: 7228kb

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: 215ms
memory: 7384kb

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: 193ms
memory: 7368kb

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: 199ms
memory: 7188kb

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: 199ms
memory: 7148kb

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: 27
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Test #87:

score: 27
Accepted
time: 648ms
memory: 9044kb

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:

47777
43669
1
24321
47708
5
48949
1
1
1
1
1
48711
2
3
40398
39882
48643
48
3
42626
47467
1
1
40384
44078
1
5
1
38231
35
2
48178
1
49001
1
47371
1
42207
59
48002
47820
46477
48893
1
30977
4
1
1
1
10
3
1
28948
41863
1
44728
36616
19670
1
1
37397
46341
6
40231
9213
2
44246
45252
44277
47581
34595
22638...

result:

ok 50063 lines

Test #88:

score: 0
Accepted
time: 65ms
memory: 6876kb

input:

447 99681
432 259 741787656
82 143 380113631
317 104 156765724
76 270 110432834
212 261 207353276
25 300 39463185
14 56 725978322
155 236 785136504
398 265 446396092
343 1 949863738
1 110 808326751
97 180 623625192
308 92 73346434
253 252 319943247
362 372 874189144
206 402 177923890
22 205 89269820...

output:

447
447
447
447
446
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
447
...

result:

ok 5072 lines

Test #89:

score: 0
Accepted
time: 48ms
memory: 6952kb

input:

447 99681
432 259 1000000000
82 143 1000000000
317 104 1000000000
76 270 1000000000
212 261 1000000000
25 300 1000000000
14 56 1000000000
155 236 1000000000
398 265 1000000000
343 1 1000000000
1 110 1000000000
97 180 1000000000
308 92 1000000000
253 252 1000000000
362 372 1000000000
206 402 10000000...

output:

443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
443
...

result:

ok 4979 lines

Test #90:

score: 0
Accepted
time: 502ms
memory: 8876kb

input:

50000 100000
39130 22921 1
19158 41929 1
11327 27463 1
26127 21731 3
41255 16743 1
31017 33919 4
2943 38537 5
17442 3263 3
19153 29330 1
46634 25047 2
22439 28316 3
14129 36616 1
14750 22406 2
45480 12190 1
33733 569 3
27631 13529 1
18455 47269 2
45002 10708 1
42180 22768 4
18679 18316 1
23405 37647...

output:

1
46859
8597
46860
3
46860
46860
49051
49051
38776
46860
2
1
49051
49051
1
49051
46860
2
38778
8598
46860
46860
38779
46860
46860
1
46860
49051
4
1
7
49051
8598
46860
1
46860
46860
49051
49051
49051
49051
38779
18
49051
49051
5
38777
49051
1
46861
8593
8593
49051
8594
46861
38780
38780
7
3
46861
468...

result:

ok 49957 lines

Test #91:

score: 0
Accepted
time: 649ms
memory: 9036kb

input:

50000 100000
11140 33017 39866336
41493 32846 146361404
38296 4903 221787293
41454 19471 358568724
27532 16060 445279711
22057 2893 904138212
13403 48696 592528192
23296 28834 677532042
18713 35657 153628525
8961 38422 878653236
6462 11508 529858987
29152 32951 220143002
45042 6537 73248627
15244 12...

output:

1
67
1
1
46176
43119
45896
47690
48367
48950
45817
46550
47799
15
34846
46165
2
40938
42368
6
42648
1
1
1
48699
2
1
33079
2
46866
46259
48341
46033
47359
47550
43272
46386
48996
48155
39063
3
47451
1
48774
1
34663
42652
48616
1
43116
2
22195
27912
47746
48506
48300
1
45179
48978
1
48451
2
48348
1
46...

result:

ok 49957 lines

Test #92:

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

input:

50000 100000
8505 33683 1
43351 33650 1
946 31674 3
14335 6521 5
32691 25783 2
9368 29050 2
29766 2083 3
40212 16142 1
12350 43828 3
31383 26419 3
41845 30090 2
43965 14260 2
25832 40811 1
13317 49699 1
13988 32162 3
34407 24929 2
14856 40788 4
5914 30150 2
24355 41328 3
43394 22787 2
19301 45919 4
...

output:

40301
40301
2
49002
1
16973
49002
47070
47070
49002
49002
49002
49002
2
49002
49002
16974
40303
47070
16974
47070
47070
49002
1
5
40304
1
49002
49002
1
47070
49002
40304
49002
49002
49002
40304
47070
40306
1
1
1
40307
40301
40301
49002
1
16975
2
49002
16979
1
49002
1
47072
40302
49002
49002
49002
40...

result:

ok 49940 lines

Test #93:

score: 0
Accepted
time: 391ms
memory: 7308kb

input:

50000 50000
3736 32553 169778489
23007 26139 10411056
40186 22571 401039857
2639 39069 118377698
35432 9157 313845065
8260 31544 79098528
13326 5917 141427472
7936 15359 535601101
45454 1522 90157121
25530 12505 97340267
18087 40592 11887503
18292 27517 150131350
4632 40544 46991693
7644 41885 27171...

output:

4
5
1
14
1
14
2
1
3
1
3
1
1
2
2
1
2
15
13
1
5
1
1
2
4
52
1
3
1
40
3
16
3
4
3
1
14
14
9
3
2
1
1
7
3
5
19
2
10
1
1
2
2
2
1
5
4
2
1
1
1
1
747
4
76
77
1
6
3
5
2
3
2
11
6
3
7
2
1
1
2
2
6
2
1
2
1
6
2
3
1
1
1
14
2
4
36
1
3
9
2
1
5
1
2
3
3
4
1
4
2
43
1
10
4
1
5
4
1
1
4
9
3
1
1
6
10
1
2
1
2
2
6
2
4
13
2
73
1...

result:

ok 50004 lines

Test #94:

score: 0
Accepted
time: 389ms
memory: 7204kb

input:

50000 50000
5881 29974 820513720
42408 16752 365047724
40384 42667 513125501
47566 33199 142342698
46276 38165 544044440
19074 9823 297662574
36167 28102 140919742
17077 10460 971467281
27216 7591 470073150
4852 33115 360315715
3420 18168 867931915
3968 28485 492122448
7954 46373 645727425
47880 875...

output:

2
158
1
1
4
6
11
5
2
12
51
8
1
2
2
1
1
1
35
3
3
6
5
4
6
11
1
1
1
37
7
1
3
2
3
1
6
2
10
1
15
3
1
1
4
1
2
6
4
1
1
1
9
1
5
28
1
6
1
2
1
1
8
13
1
35
2
5
1
2
2
1
1
1
6
1
2
1
2
1
2
1
4
2
17
2
2
1
10
5
5
23
2
5
9
15
7
3
1
7
1
1
1
5
49
4
16
1
1
2
1
8
20
5
2
1
6
1
1
2263
1
4
1
1
2
2
1
2
21
3
6
12
2
1
2
6
1
2...

result:

ok 50004 lines

Test #95:

score: 0
Accepted
time: 432ms
memory: 7184kb

input:

50000 50000
18267 45845 33343971
23538 42299 25174954
3048 589 260983362
9866 4711 2254169
19724 9873 23227393
16745 8300 138212340
15775 42735 3176301
38590 40466 49024416
10468 1268 50359267
35366 12206 85650490
39454 25170 153352208
16164 49790 98538736
9211 16427 36617534
2039 25103 165887514
41...

output:

41
196
118
289
60
376
72
5
42
62
46
67
279
15
60
23
32
44
67
2555
10
3
81
41
1114
249
4090
390
12
58
6
4
19
37
17
26
812
1239
30
184
327
59
301
322
27
56
92
567
2555
13
42
260
25
565
313
59
102
182
354
448
59
13
8
1097
186
50
136
1
782
892
132
160
1204
591
132
980
25
210
131
1079
115
25
653
406
263
...

result:

ok 50142 lines

Test #96:

score: 0
Accepted
time: 570ms
memory: 8252kb

input:

50000 75000
19684 12711 237556528
22829 37236 16509732
9143 34310 48162977
49600 30069 11054949
35237 28953 82800199
47819 35176 52697718
15979 45278 191978666
2411 7753 844383
37017 23696 6793222
4421 23256 124463310
37732 34150 39779362
26894 46733 18891187
14077 29482 1629067
45005 29847 13681133...

output:

121
727
1
1
1
1
798
1
15
1
3
1
844
1
288
2
6
330
3
16
2
147
9
839
1
2
90
36
3096
1
1
36
118
4108
1
6
33
10
1
7
5
11
62
5714
1
7
2
1
4
3
4
1
3
1
314
2
38
5
1
160
72
1
2
6
5
1
1
24
4
8
12
1
2139
2
1
716
2
10
2
19
1
1
61
1
587
14
83
5
2
167
2
1
2
30
261
2
365
106
810
6
14
15
21
36
2
12
19
11
2
7
292
10...

result:

ok 49855 lines

Test #97:

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

input:

50000 75000
5537 13592 770047339
43864 36359 139943481
44374 21146 487326450
47583 29301 994761334
35622 6307 947798044
4493 7029 709163223
38144 24600 101398299
24370 44203 952284110
49315 49763 538586210
49142 16639 543811008
8581 39116 666550209
19881 3757 523799750
24874 23596 936952748
39857 10...

output:

45
12
1
4
23
6
1
3
2
2
62
50000
1
1731
3
9
261
4
90
4
1
42
24
10
1
1
7
6
1
3
4
9
2159
1
31
1
15
3461
208
117
14
1
3
2
5
18
7
15
14
2
12
39
6
2
1
2
2
1
1
6
1243
4
1
22
40
11
9
36
997
14
2
1
1
80
4
262
1
22
1
5755
73
5
6
1
95
12
75
220
5
3
2
1
6
1
24
2220
47
17
9
5
2
2310
56
2
1
2
47
12
16
1
4
88
118
...

result:

ok 50031 lines

Test #98:

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

input:

50000 75000
43772 5322 61245203
4500 7194 13540274
34111 7505 189284804
30030 41495 440253025
46673 26034 20152823
31803 7233 580217630
15726 5128 198793425
32708 14444 557052007
24630 30125 143816037
44937 39530 27565004
48156 35804 254143648
33814 8655 38800650
49937 3601 35746424
17330 35888 7486...

output:

1671
888
4096
4322
695
1578
3737
3438
1
30
3147
3434
3077
3167
3660
3986
642
50000
3880
3095
918
2985
88
50000
4008
3660
3705
4144
598
3132
1326
3139
156
617
3016
488
724
35533
1650
2232
3153
10948
3768
596
1326
49999
3660
4112
3147
23
3768
3986
6
3660
4076
3033
4130
3880
4096
4086
25472
4094
1719
4...

result:

ok 49844 lines

Test #99:

score: 0
Accepted
time: 318ms
memory: 8956kb

input:

50000 100000
8505 33683 4
43351 33650 2
946 31674 3
14335 6521 4
32691 25783 3
9368 29050 3
29766 2083 3
40212 16142 1
12350 43828 2
31383 26419 1
41845 30090 4
43965 14260 5
25832 40811 5
13317 49699 2
13988 32162 4
34407 24929 5
14856 40788 1
5914 30150 5
24355 41328 1
43394 22787 1
19301 45919 1
...

output:

3
49002
4
47009
47009
1
19261
19261
47009
49002
2
19261
49002
47009
47009
40673
2
49002
40673
49002
40673
49002
40673
49002
40673
40673
47009
40673
40673
40673
49002
49002
49002
19261
49002
40673
49002
49002
1
47009
49002
49002
1
49002
3
40672
49002
40672
40672
40672
49002
1
40672
49002
47009
40673
...

result:

ok 90092 lines

Test #100:

score: 0
Accepted
time: 366ms
memory: 9008kb

input:

50000 100000
8505 33683 2
43351 33650 2
946 31674 3
14335 6521 4
32691 25783 1
9368 29050 3
29766 2083 3
40212 16142 2
12350 43828 3
31383 26419 1
41845 30090 3
43965 14260 5
25832 40811 2
13317 49699 3
13988 32162 4
34407 24929 3
14856 40788 3
5914 30150 5
24355 41328 4
43394 22787 4
19301 45919 2
...

output:

1
20377
49002
49002
49002
41175
41175
49002
49002
2
47204
49002
41176
41176
49002
49002
47204
20361
49002
41179
41180
41182
41185
41185
47208
41180
2
49002
49002
47206
8
49002
41181
1
49002
13
49002
41185
3
49002
1
41180
1
47211
1
1
1
49002
49002
1
47210
47210
1
47210
49002
49002
41178
2
49002
20362...

result:

ok 9999 lines

Test #101:

score: 0
Accepted
time: 666ms
memory: 9032kb

input:

49729 99012
34054 8341 4175351
18682 17977 31563632
19269 15971 316486513
16453 23315 222200372
48031 37963 328549397
35957 4042 144188344
41481 23139 199796339
30840 7454 2956883
9107 36464 105802625
15976 35553 213475524
35520 40158 41633125
27542 9944 262538992
14658 21385 146413217
27915 22932 1...

output:

152
28
49369
40013
1
2
37355
47959
48318
40419
1
49114
5
48326
9
38504
41836
36141
48232
45058
1
44213
23736
7
2
3
1
2
2
2
1
49367
287
44956
49194
2765
36249
3252
45902
4
49665
1
31440
38388
40249
2
46768
4
1
44219
13759
47307
49641
27198
2
49100
26
3
13115
41330
1
49590
40543
49729
3
3
1
81
42709
4...

result:

ok 49858 lines

Test #102:

score: 0
Accepted
time: 646ms
memory: 8924kb

input:

49719 98972
21767 6065 50070961
20464 17361 169248081
27314 45549 36819446
33702 41335 351272826
48558 44834 199266519
30638 21034 674557652
19478 11122 253122173
29904 49011 156855128
47670 28852 109873392
17146 14684 169743003
15703 3814 7374462
16769 39749 189412976
7203 46682 136468490
46010 203...

output:

1
1597
147
27
41142
1
20984
1
48557
49659
42247
49719
41535
54
45103
1
12441
2
1
48808
1591
1
1
13552
48896
19
26143
47989
36089
34988
1
1
23177
4
39563
3
1
1
45302
2
43661
47099
12
37489
1
48238
8
49272
48896
2
3
21774
22395
49234
4
1
5
2
3
34741
31
1
49009
44276
49523
18781
44948
3
9
43349
28069
1...

result:

ok 50144 lines

Test #103:

score: 0
Accepted
time: 669ms
memory: 8828kb

input:

50000 99400
29410 30330 758567223
17803 21820 941403915
14061 46028 280515052
37193 24091 781060591
25716 20072 882860054
33445 37640 509782731
12541 23219 782716806
18523 6908 531828972
3230 32030 421168543
44552 48693 97642726
1279 2726 643181026
25106 34578 884629614
4038 37779 617488416
38071 11...

output:

49941
1
49863
46808
49431
49996
39660
2
49986
1
47338
264
3
37231
40619
49916
7
34275
1
49190
11
1
40798
3
4
6
26854
1
10
1419
76
1
1
49605
49569
45347
31859
45912
1
29
49569
1
49569
70
49778
1
3382
50000
49935
1
49116
39668
3
49890
49101
49923
49902
3847
1
50000
19
41517
1
5366
30768
4
3
18508
1040...

result:

ok 49889 lines

Test #104:

score: 0
Accepted
time: 672ms
memory: 8976kb

input:

49950 99201
36281 36503 763054174
9379 38035 472773481
25806 36188 761440834
24770 43939 593827712
44117 32984 959406044
18886 41008 690486926
49627 4512 624530349
21092 16661 833081827
14094 49233 910931467
31376 2432 747917920
26336 18969 451935820
39553 16163 535086746
26124 43554 903283220
6256 ...

output:

36
219
3
46296
1
10
49319
1
47896
5
1
1
46488
49729
49529
6907
39175
87
17
3
22087
49549
1
49941
1
44427
1
1
1
5
4563
365
57
49789
2
4
12
42
46004
44421
49848
49095
49789
26
3
49650
1
12
1
3
49867
49912
1
89
45427
3
10898
11199
1
1
49320
5
46318
49947
2
1
2
49503
48309
1
5453
4
16
49709
3
40082
1
62...

result:

ok 49970 lines

Test #105:

score: 0
Accepted
time: 608ms
memory: 8608kb

input:

49998 83327
39504 32115 603170071
49865 30849 130675480
30107 3167 55412622
33018 6097 94561562
32270 43450 124904278
1328 13459 79410517
5277 31217 436853542
22995 17298 247419872
32399 25864 535304576
20487 35769 11662754
19774 21657 33814282
4158 30463 363491899
40211 40065 187002697
22211 32071 ...

output:

13971
16568
8612
8610
48451
4960
15966
13968
13975
49998
16568
34472
33095
15966
15966
1047
15951
15966
8607
13975
4961
15951
34468
13976
8961
15966
15951
49998
1390
15950
49218
8392
49998
49998
34475
8373
6445
4961
16566
15966
49998
13971
4995
8373
8373
15951
13975
15951
558
15951
8622
15995
8956
5...

result:

ok 49960 lines

Test #106:

score: 0
Accepted
time: 585ms
memory: 8556kb

input:

49992 83306
18171 44476 566111419
14354 45323 78491664
31324 42407 86408010
16269 10214 343483203
44837 22800 14793460
45715 9529 8321488
22348 19511 683659900
7036 10120 683944755
9747 12255 43970763
37546 33897 19677943
12388 12210 109434184
24731 34404 33575744
46477 2587 10649026
26986 49355 534...

output:

9069
49992
14470
4109
13380
11002
13384
3112
13389
9107
9110
9095
3113
13378
2237
13380
11014
9094
49992
9109
9110
11014
14471
11018
13375
5470
9110
13289
8622
49992
9109
13384
11001
13375
13384
13375
13380
1116
9109
4113
13500
11001
3112
3120
9110
13398
49992
736
3113
13389
2237
1140
22122
2223
130...

result:

ok 49959 lines

Test #107:

score: 0
Accepted
time: 393ms
memory: 8580kb

input:

49991 83304
6546 24773 12088197
23803 24667 91224388
13036 6680 98795103
17715 24943 958918
18028 17662 198124379
27806 10774 108480491
26163 36038 289633368
23547 46728 166366787
37460 5639 6817318
600 25596 362221978
16852 4964 287806307
13055 6341 360799895
15363 45448 18192353
16255 49970 398759...

output:

6171
30609
2416
16417
2416
16407
16395
6171
12503
6184
16407
12508
6031
16407
2533
6186
16422
1642
16407
49991
49991
12499
16423
2522
16406
12503
2522
49990
49991
6031
12502
30609
12508
16406
16407
16404
2416
2527
297
1498
16386
30611
6062
12500
6186
49991
5964
49991
49991
16406
6031
6507
16407
2526...

result:

ok 10007 lines

Test #108:

score: 0
Accepted
time: 320ms
memory: 8380kb

input:

49993 74977
5357 45947 302533790
21280 4499 68797324
12589 43445 265044633
10737 43704 23744651
39280 27493 51987480
16749 28998 330531333
48940 47702 1609550
30567 5837 229308876
44403 29872 172344165
22668 28745 11430738
44734 33765 173246296
18322 28966 405641752
15110 30702 169253722
28413 48831...

output:

1200
34016
5551
3581
7130
6917
5551
5603
6883
49993
5551
2279
2249
5551
7090
5597
3498
7352
7090
7130
7263
7263
7263
6253
7090
7090
6920
2249
3498
6268
2263
7130
7352
5603
5596
34016
6209
34016
6907
7131
34016
6840
2249
6840
6183
6318
980
6318
5594
5596
15976
948
49993
6268
5597
7352
6100
6185
6209
...

result:

ok 5074 lines

Test #109:

score: 0
Accepted
time: 384ms
memory: 8564kb

input:

49990 83301
24842 17805 69141048
6977 49148 207860580
32755 450 19411360
46084 13712 318063909
101 1991 97946457
13359 49084 140436112
49059 291 31246303
32524 24564 452354580
9712 20838 67699521
37511 28785 19751576
12918 10769 594064435
41417 34434 45065184
14291 7476 205714546
25951 2762 55394284...

output:

49990
9948
9948
7177
7177
5466
19926
7794
18918
19926
2757
9915
7177
5379
7193
2757
7772
7130
7189
11127
49990
7177
11134
18915
8455
7136
9913
7803
11697
49987
5439
2808
7130
49987
18915
5440
2
9913
9925
49990
5440
7792
9948
7179
7177
11697
11134
49987
7177
9913
7130
49990
18919
9925
49990
11695
546...

result:

ok 90066 lines

Test #110:

score: 0
Accepted
time: 601ms
memory: 8772kb

input:

48729 95081
34569 31119 121468261
44534 42997 32387101
27645 27262 179917793
27160 40400 147086695
24917 45974 392357817
10176 23589 64525446
36132 43032 101470030
48191 26960 218513742
27615 10820 393845101
36869 33441 37211419
40354 27469 38639025
14212 10067 288238270
17744 3968 186572229
24158 3...

output:

46935
43798
48728
47759
48729
47726
43241
46497
48729
43615
48723
43970
48707
46777
47322
46031
47499
42179
46978
45561
47297
48191
46031
44602
48709
43556
48400
43030
42619
44163
47550
46384
42417
48729
48095
2
47922
42873
44175
42140
48643
48728
47606
42958
48609
44326
48227
48341
47429
47343
4569...

result:

ok 50128 lines

Test #111:

score: 0
Accepted
time: 489ms
memory: 8460kb

input:

44729 80122
5199 20293 31
7817 41640 6
34878 22640 20
40005 33324 15
40383 32872 13
34683 29204 20
27984 14878 12
30253 38386 33
25606 20784 8
2189 25911 7
2456 33868 20
11948 9644 40
20299 36926 11
33341 21039 30
32405 33498 16
19620 43993 12
6437 37553 50
13577 29531 25
18855 28841 64
10313 6994 2...

output:

44400
44630
44720
44720
44720
44400
44400
44720
44630
43932
44400
44630
44720
43932
43932
43932
44630
44720
43932
44630
44630
44630
44720
43932
43932
43932
44720
43932
44630
44720
43932
44630
44630
43932
44720
44720
44720
44400
44630
43932
44400
44720
44630
44400
44720
44630
44720
44720
44720
44630
...

result:

ok 49862 lines