QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#940928#10163. Tree QuizvolfridAC ✓310ms114888kbC++204.5kb2025-03-18 06:34:192025-03-18 06:34:19

Judging History

This is the latest submission verdict.

  • [2025-03-18 06:34:19]
  • Judged
  • Verdict: AC
  • Time: 310ms
  • Memory: 114888kb
  • [2025-03-18 06:34:19]
  • Submitted

answer

#include <iostream>
#include <vector>
#include <functional>
#include <cstdint>
#include <cmath>

#define dbg(x) std::cerr << #x << " = " << x << "\n";

using Graph = std::vector<std::vector<int>>;
using i64 = std::int64_t;

struct Node {
  int l = 0, r = 0;
  int sum = 0;
};

struct PersistentSegmentTree {
  PersistentSegmentTree(const int N, const int nodes_count) : N(N) {
    T.reserve(nodes_count);
    T.emplace_back();
  }

  [[nodiscard]] int add(const int u, const int l, const int r, const int pos, const int value) {
    auto idx = this->new_();
    T[idx] = T[u];
    if (l == r) {
      T[idx].sum += value;
    } else {
      const auto m = (l + r) / 2;
      if (pos <= m) {
        T[idx].l = add(T[idx].l, l, m, pos, value);
      } else {
        T[idx].r = add(T[idx].r, m + 1, r, pos, value);
      }
      this->pull(idx);
    }
    return idx;
  }
  [[nodiscard]] int add(const int u, const int pos, const int value) {
    return this->add(u, 0, N - 1, pos, value);
  }

  [[nodiscard]] int join(const int x, const int y, const int l, const int r) {
    if (x == 0 || y == 0) {
      return x + y;
    }
    auto idx = this->new_();
    if (l == r) {
      T[idx].sum = T[x].sum + T[y].sum;
    } else {
      const int m = (l + r) / 2;
      T[idx].l = join(T[x].l, T[y].l, l, m);
      T[idx].r = join(T[x].r, T[y].r, m + 1, r);
    }
    this->pull(idx);
    return idx;
  }
  [[nodiscard]] int join(const int x, const int y) {
    return this->join(x, y, 0, N - 1);
  }

  
  // query function somewhere in here
  std::pair<int, int> query(const int lhs, const int rhs, const int l, const int r, const int k) {
    if (l == r) {
      return {l, k};
    }
    const auto sum = T[T[lhs].l].sum - T[T[rhs].l].sum;
    const auto m = (l + r) / 2;
    if (sum >= k) {
      return query(T[lhs].l, T[rhs].l, l, m, k);
    } else {
      return query(T[lhs].r, T[rhs].r, m + 1, r, k - sum);
    }
  }
  
  std::pair<int, int> query(const int lhs, const int rhs, const int k) {
    return this->query(lhs, rhs, 0, N - 1, k);
  }
  std::pair<int, int> query(const int root, const int k) {
    return this->query(root, 0, k);
  }

  int new_() {
    T.emplace_back();
    return T.size() - 1;
  }

  void pull(const int idx) {
    T[idx].sum = T[T[idx].l].sum + T[T[idx].r].sum;
  }

  int N;
  std::vector<Node> T;
};

int main() {
  int N, Q;
  std::cin >> N >> Q;
  Graph G(N);
  int root = 0;
  std::vector<int> parent(N + 1, N);
  for (int i = 0; i < N; i++) {
    std::cin >> parent[i];
    parent[i]--;
    if (parent[i] == -1) {
      root = i;
    } else {
      G[parent[i]].push_back(i);
    }
  }

  const int max_nodes = std::ceil(1 + std::log2(N)) * N * 2;
  PersistentSegmentTree DS_lca{N, max_nodes}, DS_values{N, max_nodes};
  std::vector<int> root_lca(N), root_values(N);

  std::vector<int> subtree_size(N), depth(N);
  std::vector<std::vector<int>> up(std::ceil(2 + std::log2(N)), std::vector<int>(N + 1, N));
  parent[root] = N;
  std::function<void(const int)> dfs = [&](const int u) -> void {
    up[0][u] = parent[u];
    for (int l = 1; (1 << l) <= N; l++) {
      up[l][u] = up[l - 1][up[l - 1][u]];
    }

    subtree_size[u] = 1;
    for (const int v : G[u]) {
      depth[v] = depth[u] + 1;
      dfs(v);
      subtree_size[u] += subtree_size[v];
    }
  };
  dfs(root);

  std::function<void(const int)> dfs_build = [&](const int u) -> void {
    root_lca[u] = DS_lca.add(root_lca[u], u, subtree_size[u]);
    root_values[u] = DS_values.add(root_values[u], u, 1);
    for (const int v : G[u]) {
      root_lca[v] = root_lca[u];
      root_lca[v] = DS_lca.add(root_lca[v], u, -subtree_size[v]);
      dfs_build(v);
      root_values[u] = DS_values.join(root_values[u], root_values[v]);
    }
  };
  root_lca[root] = DS_lca.new_();
  dfs_build(root);

  auto jump_up = [&](int u, const int delta) -> int {
    for (int i = up.size() - 1; i >= 0; i--) {
      if ((delta & (1 << i)) > 0) {
        u = up[i][u];
      }
    }
    return u;
  };

  for (int i = 0; i < Q; i++) {
    i64 k;
    std::cin >> k;
    int x = (k - 1) / N;
    const int rest = (k - 1) % N  + 1;
    const auto [lca, new_rest] = DS_lca.query(root_lca[x], rest);
    int l_bellow = 0;
    if (lca != x) {
      l_bellow = root_values[jump_up(x, depth[x] - depth[lca] - 1)];
    }
    const auto [y, _] = DS_values.query(root_values[lca], l_bellow, new_rest);
    std::cout << (i64)N * N * x + (i64)N * lca + y << "\n";
  } 
  return 0;
}

詳細信息

Test #1:

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

input:

5 3
3 0 2 2 3
1
18
25

output:

0
82
124

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 1ms
memory: 3712kb

input:

1 1
0
1

output:

0

result:

ok single line: '0'

Test #3:

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

input:

300 1000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 1...

output:

5327916
21581976
15622083
20912508
10655561
19305451
24756321
15227458
7856250
25059130
5237526
22843745
20700602
18146588
21919966
19685642
25804715
1896478
296
1715722
15221438
12333311
10655625
10441505
20113645
4063673
25229197
10384687
4154043
8939986
10375284
3341178
14941505
4876355
26400100
...

result:

ok 1000 lines

Test #4:

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

input:

300 1000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 1...

output:

0
90000
180000
270602
360903
450301
541505
631204
721806
811806
900301
990903
1083010
1172408
1261806
1351806
1444515
1534214
1620000
1715117
1804816
1895117
1983913
2074515
2163612
2253311
2342408
2432709
2527826
2613010
2702408
2799331
2880903
2973311
3064515
3157224
3245719
3330903
3426923
351571...

result:

ok 1000 lines

Test #5:

score: 0
Accepted
time: 42ms
memory: 4096kb

input:

300 90000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 ...

output:

0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
10...

result:

ok 90000 lines

Test #6:

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

input:

300 100000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99...

output:

8849603
25193988
18101739
2799509
18313043
4597525
10565335
24914046
24981170
3966622
25912474
22623712
22512642
14990029
7946643
3792824
18042441
5327992
5056925
17496722
3070414
8759302
11378001
2794816
1535290
3250913
9752683
1354722
7766012
19103177
17058160
18396120
5147304
7402575
15883344
121...

result:

ok 100000 lines

Test #7:

score: 0
Accepted
time: 113ms
memory: 77520kb

input:

78389 5
33487 77089 27981 73896 46472 48234 35441 73809 65081 62732 27144 41190 22052 6601 54521 25538 12849 25139 7955 2888 560 65683 62389 20227 26954 26555 61996 34967 41099 4061 7469 29054 25664 59634 27743 75654 60836 39672 29424 68875 2276 37485 42956 67749 33929 78069 51457 46619 63053 41620 ...

output:

327753830297976
328878335134962
335576205649839
255920705404580
179116408732653

result:

ok 5 lines

Test #8:

score: 0
Accepted
time: 127ms
memory: 87196kb

input:

89272 2
32030 60254 73018 74707 67667 86264 75261 45862 64043 64540 79879 65832 62630 2067 13631 65096 49308 11346 7834 56048 14150 16979 3374 55707 47414 10398 71283 68711 78891 65285 62794 21759 74768 3046 67938 2947 81772 28664 47917 85910 59506 33994 62481 35920 28052 73386 39658 79301 21612 592...

output:

542941973345600
85461370277361

result:

ok 2 lines

Test #9:

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

input:

100000 5
27675 69722 55195 80299 45710 21002 41942 77009 19110 31701 53866 78774 21515 57725 27216 19418 54890 30039 22354 8739 53058 49967 6697 20426 53425 91335 37529 49532 60119 18191 87128 23250 8644 83001 48285 1047 2152 5845 22306 14386 12581 52946 59454 23242 80992 43593 84069 91861 39630 118...

output:

737395068445482
832495068447852
199585068418439
557998894524177
132248183586103

result:

ok 5 lines

Test #10:

score: 0
Accepted
time: 84ms
memory: 107852kb

input:

100000 5
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

output:

96555000086541
333603336014372
632375000014756
212363721937219
534215000018873

result:

ok 5 lines

Test #11:

score: 0
Accepted
time: 38ms
memory: 3968kb

input:

300 90000
0 286 46 288 233 294 121 293 13 244 219 84 27 1 7 156 235 71 227 245 37 282 18 147 53 172 300 174 156 252 27 62 246 121 296 25 5 136 164 224 17 58 56 11 217 248 82 40 36 242 84 114 205 113 210 255 90 256 195 275 147 289 277 244 121 131 104 64 49 179 70 293 169 220 1 263 188 273 194 200 118...

output:

0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
10...

result:

ok 90000 lines

Test #12:

score: 0
Accepted
time: 39ms
memory: 4096kb

input:

300 90000
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...

output:

0
301
602
903
1204
1505
1806
2107
2408
2709
3010
3311
3612
3913
4214
4515
4816
5117
5418
5719
6020
6321
6622
6923
7224
7525
7826
8127
8428
8729
9030
9331
9632
9933
10234
10535
10836
11137
11438
11739
12040
12341
12642
12943
13244
13545
13846
14147
14448
14749
15050
15351
15652
15953
16254
16555
1685...

result:

ok 90000 lines

Test #13:

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

input:

1 100000
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 100000 lines

Test #14:

score: 0
Accepted
time: 64ms
memory: 4864kb

input:

2073 100000
832 1970 962 1383 640 2021 819 739 596 1353 1226 127 1042 1115 1777 1057 1825 874 1458 679 23 1034 1060 1744 1749 1703 827 1491 242 2024 97 1152 1715 1845 1917 385 500 629 743 73 233 418 266 584 1060 629 84 138 1068 753 1002 1729 923 426 1159 1172 98 319 1632 544 364 1049 1876 664 1278 5...

output:

2473356457
7510320544
1148410040
3902998685
2751314092
8851086691
8630059007
3593589531
7671755423
3030640433
1360349742
3980350105
8552707085
5717840191
2880232970
4474542490
5168277103
293240443
2549339400
6901806956
6538631089
2880233642
138537609
4397191056
886273738
6006254262
4689409979
834213...

result:

ok 100000 lines

Test #15:

score: 0
Accepted
time: 67ms
memory: 4608kb

input:

2179 100000
569 1483 1534 514 351 656 1960 1076 1227 1116 2151 570 2134 1369 2113 1864 914 2118 1098 1779 2167 1672 2145 857 717 1228 1130 118 967 1125 232 935 1193 840 1671 2146 1878 281 1864 935 124 163 363 1825 408 448 1340 1702 1568 387 807 525 1847 932 2156 1991 1534 1543 2123 1416 1736 996 39 ...

output:

4445295736
9212328302
9896047768
5290447913
2180480946
4886864660
3395978463
5902944658
5129013649
4611760743
983975082
409462282
9359518446
3676112917
4017972425
6501197132
5902944221
1591724270
7868632887
6619622342
10242654712
3942004046
1867109450
4877091988
4682698250
3642877949
281265272
58839...

result:

ok 100000 lines

Test #16:

score: 0
Accepted
time: 54ms
memory: 5120kb

input:

2500 100000
2111 1970 613 2248 1245 829 509 618 448 2127 223 222 326 1845 907 395 238 113 661 2113 1492 1026 1065 2217 1207 1030 2277 468 85 1685 482 1394 1395 1915 466 1988 392 1068 559 381 675 578 1974 278 1028 1200 1509 1129 1663 1199 1936 2017 1018 600 2382 1194 372 1933 108 2226 1569 352 975 17...

output:

11233685873
5346186250
14977436279
139935974
977436448
5079972252
10877437406
9877437458
8477435576
6239935409
15564936573
8889935619
15246185245
5758685307
9039936022
15121185300
3477436418
9073537108
9896186418
12471187384
8639935750
7914935889
14133686886
15083686556
14534015002
6814936920
128086...

result:

ok 100000 lines

Test #17:

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

input:

2500 100000
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 10...

output:

10584621348
13472413965
3978126613
13372714085
1090626988
2659376552
7815626064
832578031
2828127419
12921875183
10921875281
1577288415
1676983293
9290916366
5353126652
13367101840
2358963585
12109375133
10079032180
6365626753
3209376427
2395065526
6090626653
3965626930
6165627304
6752700626
1320345...

result:

ok 100000 lines

Test #18:

score: 0
Accepted
time: 58ms
memory: 3968kb

input:

708 100000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99...

output:

68268538
174022270
260476484
125454964
120806751
312673168
46181660
121979781
221226166
185503839
171173032
278093057
328026594
259520126
253761532
320957141
107422243
95877093
201184114
20079172
261528009
208309578
124442510
115370837
353540719
147482929
201291364
153101818
18573541
292796314
21233...

result:

ok 100000 lines

Test #19:

score: 0
Accepted
time: 60ms
memory: 3940kb

input:

582 100000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99...

output:

109573424
182442226
95006172
58292593
11876236
74951867
46824750
88559204
173645313
112310867
170527420
73968956
57003622
14251173
93648756
9161348
57343136
71197919
72604119
92631110
82790949
157027432
136509853
85844930
93159594
49199924
145902062
182416574
125449727
161244867
107159797
22055435
6...

result:

ok 100000 lines

Test #20:

score: 0
Accepted
time: 68ms
memory: 5504kb

input:

2500 100000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

5577231025
168819786
1744449620
5070779744
2507253973
4014107417
10920663265
2438476111
10387987695
7790616882
14676933273
1144208955
13749249933
4245448686
2788130252
11419130152
9972739287
12121891256
1882004227
9152993697
10702420968
11765933873
12048061724
6852741361
8538612945
350141586
6233743...

result:

ok 100000 lines

Test #21:

score: 0
Accepted
time: 289ms
memory: 99244kb

input:

100000 100000
0 1 2 2 2 3 2 7 6 3 2 7 1 5 6 13 13 1 13 18 9 4 3 9 3 21 12 15 10 23 22 4 9 7 34 19 8 29 38 4 2 35 40 15 32 22 20 12 47 40 3 21 17 4 41 54 34 19 52 40 22 39 39 48 51 37 20 11 61 10 69 64 3 53 66 58 29 43 34 10 26 49 72 71 83 14 72 70 44 17 76 38 55 6 12 47 6 23 70 4 56 41 43 46 92 18 6...

output:

986070000179396
492340096911422
303520000074342
797410000072372
433100000118856
356010000039327
517370000119116
210810000071160
627830000247183
659030000144681
460850000168510
793200000047403
734670000238718
988950000078617
493460000183748
396320000086509
885910000137731
843760000280561
772130000103...

result:

ok 100000 lines

Test #22:

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

input:

100000 100000
0 1 1 2 1 5 5 4 5 8 10 9 4 3 14 11 5 3 9 17 18 16 19 18 7 8 6 13 3 3 24 6 2 2 14 17 25 36 13 2 38 7 39 16 1 44 22 5 9 26 42 34 43 9 10 15 31 51 48 27 32 9 50 9 56 11 3 25 46 50 18 62 12 31 55 29 8 46 16 79 29 55 6 37 62 21 7 36 7 75 46 70 10 22 79 22 1 34 8 20 75 81 58 45 34 43 83 80 7...

output:

668070000012365
67730000483506
743540000011350
603150000047610
549350000058528
402230001384886
642680000482786
621500000030266
650810000038840
98060000335634
263450000027968
601710000000962
507370000330570
975120000081315
999470000072123
273670000027172
933170000007120
453530000096371
92400000471956...

result:

ok 100000 lines

Test #23:

score: 0
Accepted
time: 310ms
memory: 109024kb

input:

100000 100000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98...

output:

730993778455059
497144971450450
173961739683823
337253372583836
830565545455454
364711871186527
684100827308273
81260812618822
548822019889630
238322383226753
300940021079212
152501525093297
529550241302413
868084675982979
607683328484986
507854180241802
648444273271337
323323233283004
9685331925770...

result:

ok 100000 lines

Test #24:

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

input:

100000 100000
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

0
10000000000
20000000000
30000000000
40000000000
50000000000
60000000000
70000000000
80000000000
90000000000
100000000000
110000000000
120000000000
130000000000
140000000000
150000000000
160000000000
170000000000
180000000000
190000000000
200000000000
210000000000
220000000000
230000000000
24000000...

result:

ok 100000 lines

Test #25:

score: 0
Accepted
time: 242ms
memory: 72860kb

input:

73833 100000
8431 69701 40277 61730 13590 69377 40722 8407 408 18996 22602 34602 61242 51292 34555 1285 31780 20879 7777 28091 64913 56889 42826 10459 35408 33573 8256 68996 4979 31117 5949 40457 15241 44609 7514 25154 38357 21064 34480 42874 67193 22339 65981 61173 53924 12698 54960 24701 8163 4801...

output:

160517072750124
212782861446427
6630599762251
326689413053377
361070837164955
74081071486500
301166370783292
229296274855925
225796230073177
233875376880191
304284521185146
260614061660965
163918691359171
178811675495487
239615608293908
83534452530030
176200497064051
109165714798692
202437661171238
...

result:

ok 100000 lines

Test #26:

score: 0
Accepted
time: 171ms
memory: 42324kb

input:

43956 100000
26202 39174 37007 4677 14241 34149 42008 11821 8619 27454 7175 39248 19087 22731 27928 7350 9923 30873 26847 35565 25374 24253 13216 30162 43221 23688 37036 1370 43774 20025 12026 12583 10594 17822 3590 43198 7523 6345 15628 21833 41390 27701 18336 26734 8715 18562 21901 18883 11935 307...

output:

6636151170599
43905439460095
25112920739660
70431669926807
14134972967086
13891026402808
66299378575324
29672747405721
21597085792361
20961188035221
494364028041
48786018256460
30693553559882
65959996032786
38342855986344
74490433402530
59189896421618
79011617454663
10121524588762
26178165906897
807...

result:

ok 100000 lines

Test #27:

score: 0
Accepted
time: 278ms
memory: 99260kb

input:

100000 100000
70055 55618 94565 83769 73623 5096 22162 89981 93964 48846 7488 82440 5700 45126 36278 63360 6088 51317 81136 87634 86943 27607 45494 56948 69588 87252 21050 20154 62076 47647 92496 3788 33944 17980 96965 43746 82198 17896 73241 66164 39010 81126 67039 8956 61497 89492 60451 61521 5019...

output:

670550764716726
108532846478425
431502846463728
597000764730883
568231178544842
49160764792803
96560764766158
254752846412647
189290764720557
611210764780997
971190764724091
927374606418009
909979823399034
589052846422525
828009823356578
556462846442324
545136875819453
524190764758014
50739076472306...

result:

ok 100000 lines

Test #28:

score: 0
Accepted
time: 241ms
memory: 107856kb

input:

100000 100000
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 ...

output:

824025000042852
394265000098183
564845648487907
507705077055509
963867215372153
951465000044644
440385000078481
727235000041970
433884338804989
420925000070234
837345342653426
806395701157011
314205000082821
662535358353583
624896248995053
10795000066591
644765882258822
186291862915251
1526131149311...

result:

ok 100000 lines

Test #29:

score: 0
Accepted
time: 72ms
memory: 5376kb

input:

2500 100000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

2438476020
8945685774
9789134937
13402378451
1162967276
11876190476
12301450580
4701881156
13100604169
3226291257
1469339154
6989965986
13163475390
10613022185
4107894049
8901918267
10458700980
3119998455
4789283213
8672073829
9401579258
14519788207
14258313325
1818932573
14020790816
2057073800
7108...

result:

ok 100000 lines

Test #30:

score: 0
Accepted
time: 45ms
memory: 4096kb

input:

300 90000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 ...

output:

0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
10...

result:

ok 90000 lines

Test #31:

score: 0
Accepted
time: 114ms
memory: 109060kb

input:

100000 5
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 1...

output:

158841588420207
185321455014550
823911825962554
24700247088316
853221915123477

result:

ok 5 lines

Test #32:

score: 0
Accepted
time: 211ms
memory: 98500kb

input:

100000 100000
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

548810000039251
844260000072433
544880000023084
623560000023968
437580000039023
56710000001546
383440000030358
812160000038982
568040000052578
836070000028209
87120000000176
368240000035247
778150000067700
870080000041208
799150000036879
520470000035334
118270000007568
582010000031276
94466000004929...

result:

ok 100000 lines

Test #33:

score: 0
Accepted
time: 213ms
memory: 98500kb

input:

100000 100000
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

932340000062349
827090000007925
505740000021848
205090000055212
854270000065769
488830000098178
259900000022726
282160000079108
456030000063664
399050000098247
50950000014444
8810000061713
820320000063194
724660000085464
709360000023248
662950000062914
133400000073639
919270000080308
210400000057041...

result:

ok 100000 lines

Test #34:

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

input:

300 90000
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
10...

result:

ok 90000 lines

Test #35:

score: 0
Accepted
time: 43ms
memory: 3968kb

input:

300 100000
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

8460115
15660184
6570165
12780072
22590162
10980177
25470214
13410161
6840241
13860171
4770178
20700144
7650220
4230129
16200089
2250054
11610251
19710155
5310147
8370128
25650120
16740021
12330148
6120026
2790152
22500078
18450057
25200125
24660288
18270255
4050017
5670236
15930168
13320014
9090124...

result:

ok 100000 lines

Test #36:

score: 0
Accepted
time: 268ms
memory: 114888kb

input:

100000 100000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98...

output:

260352603539847
894388943899899
873765160451604
435394353968550
321763217650084
924984691346913
253782537849124
237640646006460
220682206830537
322253222542120
582982846328463
500443446434464
829571543715437
858334507045070
894011489014890
654850487404874
984601036210362
49260492655307
5113412711127...

result:

ok 100000 lines

Test #37:

score: 0
Accepted
time: 244ms
memory: 114888kb

input:

100000 100000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98...

output:

0
10000000000
20000000000
30000100001
40000100001
50000400004
60000500005
70000200002
80000000000
90000700007
100000000000
110000800008
120000500005
130000700007
140000500005
150000800008
160000900009
170001500015
180000900009
190001900019
200000800008
210000200002
220000300003
230001400014
24000210...

result:

ok 100000 lines