QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#292187#6332. Two Currencieschy12321100 ✓381ms103404kbC++202.4kb2023-12-27 20:13:252023-12-27 20:13:25

Judging History

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

  • [2023-12-27 20:13:25]
  • 评测
  • 测评结果:100
  • 用时:381ms
  • 内存:103404kb
  • [2023-12-27 20:13:25]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

constexpr int N = 1e5 + 10, K = 17;

int n, m, q, w[N], rt[N], dep[N], fa[N][K];

struct Edge {
    int u, v;
} e[N];

vector<int> G[N], H[N];

inline void add(int u, int v) {G[u].emplace_back(v), G[v].emplace_back(u);}

namespace PST {
    int tot;

    struct Seg {
        ll w; int sz, ls, rs;
    } t[N * 40];

    int newt(int pos) {t[++tot] = t[pos]; return tot;}

    void upd(int &pos, int l, int r, int x) {
        t[pos = newt(pos)].w += x, t[pos].sz++;
        if (l == r) return; int mid = (l + r) >> 1;
        x <= mid ? upd(t[pos].ls, l, mid, x) : upd(t[pos].rs, mid + 1, r, x);
    }

    int query(int u, int v, int lca, int l, int r, ll c) {
        if (l == r) return min(c / l, (ll)t[u].sz + t[v].sz - 2 * t[lca].sz);
        int lsz = t[t[u].ls].sz + t[t[v].ls].sz - 2 * t[t[lca].ls].sz;
        ll tmp = t[t[u].ls].w + t[t[v].ls].w - 2 * t[t[lca].ls].w;
        int mid = (l + r) >> 1;
        if (tmp > c) return query(t[u].ls, t[v].ls, t[lca].ls, l, mid, c);
        return lsz + query(t[u].rs, t[v].rs, t[lca].rs, mid + 1, r, c - tmp);
    }
}

void dfs(int u) {
    for (int k = 1; k < K; k++) fa[u][k] = fa[fa[u][k - 1]][k - 1];
    for (int v : G[u]) if (v != fa[u][0]) fa[v][0] = u, dep[v] = dep[u] + 1, dfs(v);
}

void dfs2(int u) {
    w[u] += H[u].size(), rt[u] = rt[fa[u][0]];
    for (int c : H[u]) PST::upd(rt[u], 1, 1e9, c);
    for (int v : G[u]) if (v != fa[u][0]) w[v] += w[u], dfs2(v);
}

int LCA(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int k = 16; k >= 0; k--) if (dep[fa[u][k]] >= dep[v]) u = fa[u][k];
    if (u == v) return u;
    for (int k = 16; k >= 0; k--) if (fa[u][k] != fa[v][k]) u = fa[u][k], v = fa[v][k];
    return fa[u][0];
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> m >> q;
    for (int i = 1; i < n; i++) cin >> e[i].u >> e[i].v, add(e[i].u, e[i].v);
    dfs(1);
    for (int i = 1, id, c; i <= m; i++) {
        cin >> id >> c;
        if (dep[e[id].u] < dep[e[id].v]) swap(e[id].u, e[id].v);
        H[e[id].u].emplace_back(c);
    }
    dfs2(1);
    while (q--) {
        int s, t, x; ll y; cin >> s >> t >> x >> y;
        int lca = LCA(s, t), rest = x - (w[s] + w[t] - 2 * w[lca] - PST::query(rt[s], rt[t], rt[lca], 1, 1e9, y));
        cout << max(-1, rest) << '\n';
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 2ms
memory: 12260kb

input:

1831 1865 1153
832 1698
1672 1619
634 920
328 1244
571 1279
1673 1815
1098 92
1320 432
244 636
991 1446
308 569
1118 1356
1733 71
497 1679
1699 635
1254 1295
853 345
364 1396
1183 1134
524 1557
1642 1262
1767 459
918 794
1644 539
902 1046
334 1789
1691 1548
1298 520
1763 216
1161 1065
682 1167
1282 ...

output:

378730605
649537044
339843141
362013697
600127619
123276007
749019778
22
30
54569538
-1
26669081
33
255375699
0
7
8
-1
427653834
2
9
19
7
9
-1
8
6
265022184
218253041
-1
24
849614439
9
29092527
539604026
0
6
-1
6
-1
12
8
-1
22
-1
13
11
26
7
-1
2
0
546008661
4
6
86261072
-1
448122840
873577464
-1
0
1...

result:

ok 1153 numbers

Test #2:

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

input:

1942 1832 1894
1076 1725
1111 725
1093 19
921 1759
1917 1017
1854 724
901 1713
58 1482
1469 134
1463 1030
159 162
3 570
781 1533
64 1043
1693 894
329 1075
252 1727
1579 213
1051 419
67 80
351 1739
990 313
1545 94
680 649
1769 140
678 1755
602 17
598 476
586 509
1321 1535
402 949
1135 1196
1668 985
1...

output:

290930763
222025343
905421625
3
2
691499099
9
-1
-1
923482030
11
11
22
10
1
5
12
13
230762895
808118430
470508163
-1
-1
5
769521091
1
649347743
867764525
3
4
9
-1
635895869
518880732
-1
161787337
812530072
-1
7
8
25
-1
5
6
0
3
655886721
576512193
3
440416008
7
8
-1
-1
-1
11
11
3
-1
418197782
5773691...

result:

ok 1894 numbers

Test #3:

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

input:

1259 1420 1830
767 33
409 881
144 630
754 665
98 954
1133 741
163 1011
351 474
1165 168
213 70
1257 801
654 727
336 1238
147 756
956 639
540 671
1049 837
967 768
275 565
480 791
922 739
504 906
281 683
1069 1019
1195 716
851 45
119 515
1226 997
153 1163
1180 333
941 649
32 1199
1118 699
144 181
675 ...

output:

20
293315087
17
214464390
1
7
1
1
463782411
193462252
-1
264243615
238908207
-1
578800563
1
17
20
2
-1
490218156
4
2587714
12
17716886
171554130
22
10
10
283890617
3
32583568
1
1
3
334255184
7
6
2
3
518826413
610186572
-1
3
297569392
-1
-1
0
-1
4
987836934
0
35
315447009
10
13
14
-1
-1
711900410
19
...

result:

ok 1830 numbers

Test #4:

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

input:

2000 2000 2000
439 1912
92 340
1771 416
403 550
885 1093
1664 1308
124 506
1535 1848
1806 1245
1057 791
805 1930
1607 1456
1795 1409
969 1527
471 1553
1794 1721
1967 829
979 243
1360 295
392 911
963 1566
1815 663
356 770
23 924
964 1883
1668 1499
1514 927
412 1764
1270 418
649 369
1828 1958
687 428
...

output:

16
18
6
-1
7
-1
14
0
17
10
8
16
4
-1
11
9
6
7
9
27
0
17
1
-1
22
29
-1
-1
-1
5
0
3
-1
-1
4
22
4
1
5
7
15
8
14
-1
7
11
9
1
12
17
-1
10
15
5
17
-1
1
1
18
-1
13
7
-1
4
18
2
13
-1
-1
5
13
3
5
-1
13
0
13
5
5
4
-1
22
11
-1
6
20
10
9
-1
-1
2
24
1
-1
0
3
1
4
-1
2
-1
14
15
6
-1
9
17
3
4
4
10
11
-1
2
9
-1
-1
1...

result:

ok 2000 numbers

Test #5:

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

input:

2000 2000 2000
1908 583
1115 1046
1858 74
587 1569
549 1911
1350 1887
1101 277
396 1518
569 1528
988 150
1559 1967
683 484
1569 1050
1864 1335
1218 52
1600 925
1047 90
1870 1263
157 185
141 1388
316 102
1903 1907
124 1179
1172 1928
1730 1398
1226 1976
450 657
1830 821
275 459
1382 634
1458 297
1212 ...

output:

24
2
1
-1
8
-1
-1
11
4
15
21
6
2
-1
2
3
-1
18
-1
0
-1
6
-1
21
-1
17
-1
9
-1
-1
-1
6
-1
3
15
-1
10
-1
7
-1
0
6
14
8
1
15
5
-1
-1
7
-1
-1
5
0
20
7
-1
-1
7
7
5
-1
11
3
-1
2
16
-1
-1
8
0
5
7
-1
9
14
2
2
11
-1
10
3
11
-1
6
12
12
34
8
-1
6
-1
-1
12
-1
2
4
2
19
-1
-1
0
8
-1
13
-1
0
2
14
29
25
3
1
13
15
13
...

result:

ok 2000 numbers

Test #6:

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

input:

2000 2000 2000
1532 700
306 1701
1697 1130
2000 1322
661 231
77 683
1773 1224
634 1533
155 1831
1418 1618
1945 1255
607 1006
432 20
298 1250
1180 1430
1796 142
144 1379
1713 583
1583 80
1552 1280
1327 1705
1861 517
337 725
669 303
1974 628
1176 829
1258 251
172 1757
1737 1486
1585 597
1440 1552
1610...

output:

1
20
-1
-1
-1
7
0
0
-1
13
7
6
2
-1
5
6
8
-1
1
7
11
-1
-1
-1
6
8
-1
-1
2
-1
6
10
10
-1
16
16
-1
-1
0
8
-1
-1
12
15
8
10
1
23
7
9
6
3
14
8
0
5
7
3
8
12
-1
10
1
4
-1
24
-1
22
-1
0
10
0
-1
1
23
2
2
-1
1
13
3
4
5
-1
14
4
7
-1
2
11
9
13
15
9
4
-1
7
6
3
16
1
0
7
5
11
1
32
3
26
-1
-1
8
11
3
4
2
13
9
10
-1
2...

result:

ok 2000 numbers

Test #7:

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

input:

2000 2000 2000
241 900
1930 1379
1438 670
667 1290
733 1932
1295 1721
855 1330
850 601
1751 716
1081 1571
1983 717
1269 1751
1288 69
333 714
1202 600
1447 576
1745 383
151 1669
1565 1814
689 1870
648 1217
1529 1190
957 1840
1130 1713
1660 558
102 1316
1784 973
1057 1072
113 1883
766 1033
182 326
121...

output:

7
11
31
-1
28
25
25
7
4
-1
-1
-1
-1
19
-1
9
2
0
7
13
1
17
4
4
59
17
2
8
36
0
0
10
2
-1
9
14
13
2
1
-1
11
7
-1
-1
3
0
18
-1
0
8
1
29
24
15
6
13
29
10
15
3
3
6
3
43
-1
1
-1
-1
5
17
-1
3
5
14
10
12
16
4
15
7
9
18
0
14
6
11
-1
9
15
-1
-1
21
0
20
15
11
14
18
32
-1
13
6
-1
-1
23
11
-1
13
-1
6
5
-1
12
7
1
...

result:

ok 2000 numbers

Test #8:

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

input:

2000 2000 2000
1453 1310
1106 1265
57 520
1265 300
461 1199
1805 139
62 628
1923 1503
703 1334
10 141
942 1165
1850 983
475 1937
1821 954
1771 752
825 1914
1534 944
452 1551
1532 1010
724 1212
323 1637
1159 65
312 621
1633 581
1096 1964
889 1083
857 1590
1367 1329
30 36
286 507
174 1681
413 840
592 ...

output:

4
-1
-1
-1
9
14
5
6
22
-1
-1
34
20
-1
35
0
16
9
7
14
-1
9
13
0
18
6
5
-1
5
15
6
2
18
5
18
8
7
10
13
12
20
10
-1
-1
2
9
2
-1
-1
2
6
29
11
27
10
2
4
3
22
7
1
9
20
11
1
-1
2
8
16
13
-1
-1
8
21
5
-1
0
14
-1
9
9
5
21
3
8
13
24
-1
13
12
2
-1
18
27
3
9
-1
10
12
-1
9
-1
-1
4
-1
10
12
8
11
-1
6
5
5
7
15
0
-1...

result:

ok 2000 numbers

Test #9:

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

input:

2000 2000 2000
322 586
1516 535
436 1706
471 1457
1013 1890
787 511
1276 49
43 1558
1869 822
1599 1671
1139 1791
1385 720
522 524
1537 1720
1641 570
1987 1657
1244 1000
266 1703
1987 1586
134 89
1226 1343
1316 823
1505 890
123 662
1154 607
1349 1847
1379 1072
1483 414
97 1549
861 869
1807 169
794 82...

output:

1710
220
-1
447
10
1456
480
78
411
-1
81
274
-1
-1
184
1889
73
-1
-1
-1
45
-1
184
697
251
555
149
27
20
503
213
181
490
1290
156
108
-1
-1
138
512
128
1013
378
968
-1
52
764
404
274
-1
119
2178
-1
-1
1667
-1
845
235
1358
37
201
-1
-1
1199
1504
-1
309
1040
1438
-1
80
-1
-1
1346
-1
352
683
1017
-1
12
...

result:

ok 2000 numbers

Test #10:

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

input:

2000 2000 2000
1564 687
910 825
141 1628
1559 423
968 936
621 1039
313 1740
910 23
1665 1510
807 1509
218 992
1668 37
250 1361
1924 1002
1031 406
177 86
1250 1886
1904 534
801 524
1902 484
1527 520
1210 115
652 1086
1413 239
1223 966
1985 165
760 554
1357 751
1232 913
513 1189
1433 474
480 1782
464 ...

output:

1360
-1
69
320
398
486
853
300
579
600
956
1447
142
83
115
305
53
864
83
24
447
190
-1
1212
36
128
155
-1
-1
245
388
-1
-1
1215
38
37
3
3
805
610
70
-1
380
146
157
87
-1
1057
1525
-1
423
559
5
204
517
723
63
1442
70
110
441
15
1116
-1
-1
203
-1
1044
-1
89
119
524
1080
1648
213
395
344
1095
788
164
8...

result:

ok 2000 numbers

Test #11:

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

input:

2000 2000 2000
1509 92
1257 1098
1768 1647
359 654
1743 1459
968 1397
1010 58
1725 70
1808 22
1262 1492
118 191
1455 618
827 1723
1775 246
14 824
325 1660
1821 1246
855 246
1189 1011
926 310
782 811
190 8
1949 1001
1210 1383
884 23
408 1294
221 312
1056 1294
1731 1698
1521 1069
248 1514
1747 153
152...

output:

-1
262
251
-1
18
164
268
-1
27
246
50
120
331
65
-1
49
321
512
7
14
227
151
110
0
343
1
68
188
196
-1
-1
164
110
134
241
379
39
473
16
155
58
454
29
-1
-1
621
126
392
8
-1
364
539
595
507
188
-1
174
337
-1
526
493
323
162
104
-1
256
220
-1
257
307
146
494
-1
256
65
10
170
-1
-1
142
39
34
459
158
490...

result:

ok 2000 numbers

Test #12:

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

input:

2000 2000 2000
598 1485
5 1107
1741 985
819 1339
126 1615
712 725
121 1355
821 1194
1924 1438
175 70
1846 1508
216 741
1624 1154
891 394
1993 45
1878 269
1931 1443
385 669
576 1307
1823 1002
1349 1641
808 1086
397 1906
508 1910
122 1973
1913 972
291 900
1865 88
553 202
854 1437
482 554
1398 868
347 ...

output:

300
208
34
35
259
65
-1
76
32
333
362
250
12
-1
75
335
-1
12
-1
468
-1
-1
-1
11
123
193
-1
523
79
133
139
456
-1
366
-1
362
-1
81
357
140
115
452
4
104
-1
78
160
110
376
52
120
231
336
329
359
-1
94
-1
19
-1
50
119
-1
67
183
135
124
90
352
82
359
-1
370
667
103
28
207
50
132
279
-1
-1
68
355
275
147...

result:

ok 2000 numbers

Test #13:

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

input:

2000 2000 2000
1057 1968
457 468
920 715
56 1653
1457 229
581 1751
1289 1738
268 403
1254 1996
1878 1456
1891 250
200 1729
651 1667
1870 1125
596 1287
1166 556
1783 1201
837 703
426 1523
1730 1151
1154 564
892 1273
1068 440
1481 248
241 1861
704 1556
720 1960
91 1535
75 221
1436 1561
1133 965
468 15...

output:

174
243
113
81
488
81
54
20
37
121
-1
108
39
51
-1
77
163
234
185
38
176
43
3
104
96
167
158
18
22
-1
13
-1
-1
101
-1
31
82
9
0
220
197
155
-1
83
32
48
248
144
36
200
240
241
3
-1
47
62
196
17
-1
80
176
40
-1
26
192
100
199
19
8
-1
78
-1
514
141
9
-1
5
138
-1
129
209
-1
-1
325
-1
-1
247
170
383
66
6...

result:

ok 2000 numbers

Test #14:

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

input:

2000 2000 2000
817 926
1659 1203
1736 806
1653 705
1801 1424
476 698
115 392
269 96
391 1094
419 1683
1079 1216
1080 1378
1846 492
837 871
1237 498
1307 1367
929 734
1149 1000
721 118
757 567
843 985
665 1662
1422 1418
79 1326
28 801
1 254
1821 1901
1737 747
726 292
1607 52
1321 1049
943 1543
1527 7...

output:

-1
-1
57
35
2
-1
298
-1
-1
320
408
95
45
-1
42
463
578
-1
39
423
290
-1
184
105
235
-1
-1
311
-1
663
270
0
518
7
66
471
107
307
166
633
168
190
136
-1
174
-1
330
59
324
-1
199
-1
356
61
155
510
107
702
-1
-1
-1
-1
54
174
407
75
144
461
-1
96
-1
513
66
-1
187
-1
-1
139
54
499
-1
611
-1
-1
243
504
-1
...

result:

ok 2000 numbers

Test #15:

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

input:

2000 2000 2000
1681 700
1949 700
1904 700
700 1715
700 46
1 700
700 870
1044 700
700 586
700 766
731 700
700 720
700 313
700 1064
1459 700
189 700
700 1063
700 113
891 700
700 141
700 1073
700 510
700 989
700 683
700 1328
1513 700
1096 700
618 700
700 509
919 700
196 700
700 1672
700 1763
1733 700
9...

output:

0
2
1
0
3
4
0
-1
1
1
1
-1
2
1
-1
1
0
0
2
0
4
2
-1
-1
1
1
2
2
0
6
3
-1
-1
1
0
1
0
1
0
4
0
4
0
0
0
-1
0
-1
3
0
0
0
2
-1
0
1
-1
-1
-1
1
0
0
0
3
1
2
1
0
0
0
0
0
-1
0
0
0
3
4
0
0
-1
-1
1
-1
2
-1
0
-1
0
-1
1
0
2
-1
-1
1
0
0
1
2
0
2
-1
1
6
-1
0
1
-1
2
-1
0
4
0
-1
3
0
1
1
2
-1
0
3
0
0
1
1
-1
2
5
0
4
4
1
0
0...

result:

ok 2000 numbers

Test #16:

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

input:

2000 2000 2000
1523 891
1530 891
891 1477
1199 891
891 1499
891 326
1043 891
1629 891
891 1686
891 1334
891 795
1483 891
1618 891
1243 891
1482 891
891 606
96 891
891 1904
1750 891
401 891
891 1456
891 859
769 891
891 1663
891 70
891 161
891 559
891 217
891 571
1699 891
891 250
1655 891
1648 891
184...

output:

0
-1
-1
-1
0
6
1
3
1
-1
0
1
4
-1
0
2
1
2
0
2
6
0
1
-1
-1
-1
0
1
0
-1
0
6
5
0
-1
1
-1
0
-1
2
4
-1
-1
0
5
1
1
-1
1
3
2
0
-1
-1
2
1
2
-1
1
2
0
2
1
0
2
2
3
2
0
-1
-1
-1
-1
-1
2
0
0
0
-1
0
0
-1
-1
2
1
0
0
2
-1
3
0
-1
-1
0
0
2
-1
2
0
-1
2
2
5
-1
0
-1
0
5
0
1
0
3
-1
2
0
1
1
0
3
-1
0
-1
1
2
0
0
2
0
0
3
4
-1...

result:

ok 2000 numbers

Test #17:

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

input:

2000 2000 2000
1284 391
1284 555
1284 1509
1577 1284
763 1284
1284 332
1284 570
1284 1101
1761 1284
1759 1284
1529 1284
1284 1466
4 1284
1284 744
142 1284
1765 1284
1015 1284
1284 1189
1747 1284
1386 1284
1284 606
124 1284
1284 768
1020 1284
1284 379
1284 1914
1652 1284
129 1284
1032 1284
1284 70
12...

output:

0
1
0
-1
1
1
1
1
0
0
1
3
1
3
1
4
0
0
-1
0
3
1
1
0
0
0
1
-1
0
1
0
1
2
3
0
1
-1
0
2
1
-1
0
0
5
4
0
0
2
-1
5
5
2
0
0
3
6
3
1
0
-1
5
0
-1
3
0
0
3
2
2
3
3
0
1
-1
0
-1
0
0
0
1
-1
4
2
4
2
0
1
-1
4
0
0
0
1
0
2
1
0
0
2
4
0
1
0
0
-1
-1
1
8
3
3
1
-1
4
3
2
2
2
1
0
-1
11
0
1
0
1
-1
3
2
3
0
-1
0
-1
1
1
-1
0
1
0
-...

result:

ok 2000 numbers

Test #18:

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

input:

2000 2000 2000
1197 238
814 238
1746 238
321 238
238 797
776 238
238 109
238 285
724 238
238 149
238 1737
238 249
238 473
238 420
699 238
779 238
304 238
889 238
238 1626
238 923
238 1810
1120 238
1463 238
437 238
238 1779
238 929
238 949
238 1483
223 238
1544 238
238 981
1978 238
293 238
494 238
17...

output:

0
0
0
4
-1
0
-1
1
2
2
0
0
-1
1
3
2
1
2
1
-1
0
2
0
-1
-1
1
2
-1
3
-1
-1
1
3
2
-1
4
-1
0
1
5
-1
2
1
0
0
-1
1
2
0
4
-1
0
-1
1
3
0
-1
-1
3
-1
0
0
6
0
0
0
1
-1
0
0
0
2
0
1
-1
1
2
0
-1
3
3
4
0
0
0
5
1
0
0
3
0
2
1
2
-1
2
0
1
2
0
2
1
0
0
4
0
-1
0
-1
0
0
2
1
3
1
0
-1
1
0
0
0
3
4
6
-1
2
-1
-1
0
3
0
-1
1
-1
3
...

result:

ok 2000 numbers

Test #19:

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

input:

2000 2000 2000
23 1970
854 76
1538 706
612 807
900 1523
258 1046
738 1821
541 931
762 1406
1205 1080
1006 211
810 1190
39 1727
397 850
572 569
1447 1745
1057 1400
1459 696
1822 1309
1703 1833
1611 683
1362 579
1426 63
261 271
1418 1587
814 309
224 1327
1166 1239
113 1581
14 895
1098 267
368 1340
163...

output:

1528
-1
3
-1
491
5
1291
929
1412
1161
2
9
-1
-1
-1
4
842
-1
578
1385
4
-1
-1
6
1629
-1
-1
9
183
4
7
0
-1
280
-1
677
-1
922
1156
775
-1
-1
11
9
1573
200
-1
1698
452
611
1
-1
737
1104
9
-1
4
542
10
-1
3
1
488
380
-1
13
5
-1
1434
798
543
589
4
-1
-1
1
6
7
-1
-1
-1
523
5
-1
1756
801
1
372
1101
1593
3
10...

result:

ok 2000 numbers

Test #20:

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

input:

2000 2000 2000
123 1636
53 1142
1587 1681
1871 481
959 634
1162 342
815 1745
663 794
122 863
1809 581
179 1822
26 1072
478 513
564 1116
1751 383
834 222
1805 5
1483 1517
1283 833
1191 209
621 780
1665 1047
205 14
1826 480
170 203
1095 1276
542 470
750 1760
539 573
1728 219
1756 1898
906 1616
884 190...

output:

0
1
3
3
0
-1
-1
1507
709
878
1
-1
-1
6
-1
5
10
10
0
16
-1
1798
-1
3
-1
7
1142
3
-1
-1
7
2
1
405
0
-1
3
1257
10
-1
54
-1
-1
3
488
6
1243
-1
-1
-1
2
964
4
988
-1
1309
1379
3
2
1810
2
2
27
188
0
-1
-1
1293
494
559
1
475
511
5
-1
6
3
-1
663
9
-1
1185
7
6
-1
232
3
-1
-1
-1
406
-1
1
-1
6
1
3
492
76
3
-1
4...

result:

ok 2000 numbers

Test #21:

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

input:

2000 2000 2000
799 1750
150 482
1299 1970
1106 1409
1392 167
324 693
584 555
1703 1440
62 1001
1681 1652
145 371
1019 1842
1041 512
1263 81
1816 435
7 1470
1301 857
1506 1742
1759 1891
1245 1968
616 913
1653 1282
1014 143
1501 1753
1248 1444
875 1668
1382 1426
132 1260
264 1707
497 1124
1073 1926
56...

output:

0
-1
-1
1
482
6
4
0
386
4
2
652
0
4
160
0
-1
-1
3
0
758
900
1
-1
488
-1
-1
-1
845
-1
221
-1
-1
-1
-1
5
1311
6
-1
3
1074
1086
-1
1
-1
1359
5
95
-1
-1
-1
5
0
540
228
1
820
7
646
-1
207
-1
1604
-1
-1
2
-1
-1
15
1
1031
-1
-1
222
6
-1
-1
2
-1
-1
0
5
-1
1339
-1
-1
-1
1162
462
5
97
68
5
0
977
4
-1
1
663
13...

result:

ok 2000 numbers

Test #22:

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

input:

2000 2000 2000
1853 1944
457 1237
1133 1761
1205 1106
605 1166
1175 97
722 909
681 359
852 1716
1935 268
1 1588
1900 1082
1868 588
1179 1345
1493 1106
482 52
276 156
1880 1905
497 858
290 640
1508 531
1753 1886
923 1865
661 569
1689 1787
962 992
858 1424
807 524
1212 1556
1608 1783
1251 1686
1337 30...

output:

5
-1
17
1
20
0
13
24
-1
10
4
6
8
-1
-1
5
12
16
6
14
-1
13
9
-1
20
15
7
-1
1
5
16
8
29
13
-1
-1
9
0
4
-1
24
-1
7
18
12
12
11
-1
17
0
16
18
8
10
-1
-1
0
0
19
2
12
-1
-1
-1
4
3
29
6
21
6
1
14
5
-1
7
18
12
10
18
-1
15
4
1
-1
13
12
-1
4
0
15
-1
4
4
-1
-1
14
24
17
17
25
9
24
25
7
-1
20
9
8
19
19
-1
4
14
1...

result:

ok 2000 numbers

Test #23:

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

input:

2000 2000 2000
1108 1148
1264 1635
127 216
1391 874
548 1746
855 1360
1887 1620
1 1707
1584 804
70 149
796 1344
366 764
677 1199
1247 1549
1265 1122
1052 777
1598 1340
691 1897
669 543
103 1182
1644 1774
1609 1588
1758 1736
745 1752
953 1067
1526 1391
397 908
1616 1360
1056 1657
1399 123
1783 1088
1...

output:

6
5
4
8
1
5
18
13
-1
5
1
1
-1
9
10
-1
8
-1
13
6
15
0
9
0
-1
1
-1
8
2
6
-1
6
15
11
14
0
6
-1
6
5
4
-1
3
-1
-1
2
-1
-1
2
6
-1
-1
3
11
2
9
6
8
-1
-1
13
14
0
6
10
-1
8
0
10
-1
-1
6
2
5
-1
3
6
11
9
-1
4
9
7
3
13
3
2
4
13
-1
3
-1
6
-1
3
10
7
-1
0
0
-1
0
5
2
9
5
7
11
4
0
6
8
3
6
15
3
-1
-1
-1
-1
-1
-1
4
2
...

result:

ok 2000 numbers

Test #24:

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

input:

2000 2000 2000
255 874
1314 518
1597 995
1523 580
1776 886
184 1078
1756 1297
1090 1345
797 974
816 1707
190 915
89 933
1109 615
812 148
526 1133
1212 1444
1354 1171
309 583
1693 648
1934 1728
1408 945
1099 1120
306 1526
1019 854
39 848
1517 467
472 1719
1387 1446
1411 930
1527 1512
1902 108
2000 14...

output:

-1
7
-1
-1
9
9
-1
2
-1
1
9
7
-1
12
15
16
-1
11
5
14
7
-1
1
-1
7
6
1
0
3
3
12
-1
4
11
6
4
7
7
9
-1
11
24
11
5
-1
-1
13
10
-1
-1
15
15
-1
0
6
-1
7
-1
6
-1
7
0
7
-1
-1
-1
5
4
-1
6
2
0
0
-1
-1
5
7
0
4
0
16
24
14
2
-1
17
7
4
2
8
3
-1
-1
-1
7
1
-1
12
3
4
-1
10
1
2
2
3
3
-1
7
9
-1
1
-1
13
10
25
-1
2
24
1
2...

result:

ok 2000 numbers

Test #25:

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

input:

2000 2000 2000
1489 758
1279 791
1681 1107
363 1170
1181 958
1186 897
577 1482
1540 556
810 1555
1897 580
1121 127
104 78
811 1916
1559 817
1062 112
889 769
298 343
716 660
1101 1115
801 712
1037 1332
622 1276
1322 731
430 1892
1048 1880
498 1778
1180 226
478 435
770 1750
1503 1989
854 1032
321 882
...

output:

0
0
0
0
8
0
0
21
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
6
31
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
-1
0
0
9
0
0
0
0
0
0
-1
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
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
7
0
0
0
0
0
6
0
0
0
0
0
0
0
0
...

result:

ok 2000 numbers

Test #26:

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

input:

2000 2000 2000
1561 1398
424 826
141 904
547 1655
55 634
310 555
1370 22
530 1867
1694 1314
818 698
1653 1855
1925 509
1336 278
1835 1862
1938 270
611 1312
1503 812
289 1952
473 657
831 1086
781 1062
609 1692
1693 336
197 324
1306 749
170 1584
1550 958
4 592
849 596
609 206
1470 415
1251 1619
1925 4...

output:

1
0
12
2
13
-1
-1
-1
4
9
3
4
0
11
-1
7
16
11
9
-1
25
-1
1
2
2
5
7
3
12
15
-1
2
7
-1
0
1
-1
-1
-1
-1
1
17
25
5
-1
-1
6
9
6
-1
-1
-1
17
-1
9
14
2
8
8
9
15
-1
-1
5
8
-1
-1
2
0
2
2
11
3
-1
-1
6
13
-1
4
-1
1
-1
-1
2
-1
-1
23
0
-1
1
6
10
7
-1
15
0
16
-1
1
1
6
-1
6
4
15
25
7
30
0
-1
1
17
22
-1
-1
5
-1
2
8
...

result:

ok 2000 numbers

Test #27:

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

input:

2000 2000 2000
1302 656
774 642
859 134
379 98
1620 537
1446 638
522 1333
1993 1818
1583 1629
42 1614
201 84
1211 1620
230 1431
1319 1917
1647 856
1967 1028
1872 1712
1116 1320
1322 948
1669 1943
689 871
272 656
972 113
1475 982
1579 530
1763 1418
1797 751
1864 1143
1951 782
1562 1804
510 1684
1759 ...

output:

13
13
10
-1
3
7
17
-1
23
5
3
3
0
12
8
-1
11
5
3
-1
6
7
8
2
7
8
4
1
8
5
7
18
-1
-1
11
4
4
6
12
13
-1
7
7
25
-1
11
6
11
1
4
-1
1
1
7
0
-1
-1
0
1
-1
-1
-1
14
16
4
-1
9
-1
14
3
6
16
7
21
2
-1
4
1
-1
-1
3
2
12
0
3
1
-1
8
2
-1
7
12
-1
9
13
3
8
18
4
5
-1
1
13
14
-1
14
4
0
18
10
0
9
3
11
10
12
4
3
10
6
6
24...

result:

ok 2000 numbers

Test #28:

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

input:

2000 2000 2000
221 1490
1700 403
501 1001
927 1491
165 960
1583 1136
284 446
1245 331
106 1922
995 363
1084 1011
1271 86
658 1259
681 589
756 1218
910 1716
944 1387
723 757
912 1457
773 867
1050 1825
1942 1077
186 1672
681 1401
1324 1559
374 1957
58 230
881 878
133 325
1326 1096
1475 215
549 602
185...

output:

16
0
14
0
3
3
-1
-1
11
7
-1
8
4
1
5
8
33
3
5
-1
14
15
0
8
11
13
0
0
3
-1
9
-1
0
8
13
14
-1
4
13
4
18
5
6
-1
2
8
6
1
-1
-1
16
-1
-1
0
-1
7
2
-1
14
10
3
4
15
26
5
19
3
5
-1
-1
-1
3
1
-1
13
8
5
15
-1
23
19
1
-1
-1
11
21
4
-1
-1
18
14
18
3
13
5
12
0
4
10
2
12
4
-1
13
6
8
2
3
14
8
26
-1
11
11
7
3
7
2
9
-...

result:

ok 2000 numbers

Test #29:

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

input:

2000 2000 2000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51...

output:

348
55
510
-1
248
1713
217
-1
652
-1
18
74
-1
49
137
1558
1485
901
-1
341
42
-1
-1
1081
-1
-1
-1
-1
698
87
414
128
-1
6
502
833
659
955
60
731
143
366
167
266
320
249
36
-1
203
287
345
2057
405
384
179
1138
-1
356
82
5
253
191
1254
270
401
912
452
381
665
-1
615
751
329
836
18
-1
-1
66
-1
-1
220
88
...

result:

ok 2000 numbers

Test #30:

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

input:

2000 2000 2000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51...

output:

90
1053
59
1149
-1
-1
-1
86
406
288
8
116
174
3
-1
881
-1
167
968
-1
365
-1
-1
-1
-1
-1
96
213
-1
101
-1
0
1821
-1
-1
-1
753
-1
8
-1
2496
832
-1
-1
102
139
1567
3
563
274
-1
1039
96
-1
-1
616
518
662
-1
304
-1
-1
220
1066
162
391
592
77
493
197
642
124
-1
41
821
226
-1
52
-1
-1
63
154
1514
-1
866
-1...

result:

ok 2000 numbers

Test #31:

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

input:

2000 2000 2000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51...

output:

166
312
25
35
1400
1340
-1
608
946
120
118
184
202
353
92
-1
-1
-1
627
224
213
1545
21
219
366
-1
-1
-1
474
54
95
752
4
294
108
-1
136
-1
1457
132
-1
84
-1
17
755
-1
382
5
224
-1
139
115
378
98
165
-1
133
468
144
10
896
7
29
58
-1
-1
-1
485
-1
593
-1
5
51
942
558
1218
413
1094
-1
599
1238
315
401
96...

result:

ok 2000 numbers

Subtask #2:

score: 28
Accepted

Test #32:

score: 28
Accepted
time: 135ms
memory: 87844kb

input:

99819 89735 60985
59741 24953
61387 12293
53761 1828
60970 60534
40598 48807
21876 21232
29527 13335
84269 40756
89571 12996
25757 40587
52477 63347
41372 69243
16391 58678
40854 39513
84384 91744
62938 60371
81932 45504
34121 54746
51945 14294
883 85344
78845 51797
45025 76590
37694 65493
4118 2588...

output:

36
-1
12
59
9
5
652673843
3
422622756
-1
-1
-1
29
-1
-1
-1
13
427634455
18
265926271
263974211
877045993
8
288833077
997549690
644774220
16
995218986
31
30
924036742
19
19
2
-1
10
-1
4393606
22
2
932888431
991013529
14
14
-1
6
-1
19
1
20
8
502124020
726366843
1
24
119719836
-1
25
217737158
-1
941591...

result:

ok 60985 numbers

Test #33:

score: 0
Accepted
time: 130ms
memory: 79912kb

input:

65792 82260 98345
2807 36704
10610 16927
54219 65426
24263 25305
13397 46673
60999 3285
35985 24016
10517 9010
4968 22658
30974 31951
38242 17952
61100 8530
15143 8846
61270 11644
8471 2574
41231 48185
62800 35928
39726 5051
8526 43440
35896 29662
41894 56913
52781 49717
26456 16360
32511 37106
2284...

output:

8
5
882373032
23
1
1
-1
-1
356931161
39
341872751
7
443103688
21
477952848
-1
4
-1
753271794
262323059
532395174
11
21
16
16
24
853345123
816626114
4
772964226
431526730
-1
5
21
627951453
204273333
-1
401693620
984451652
-1
-1
18
29
-1
555626761
-1
875205996
-1
117944225
125509799
15
-1
10
238336545...

result:

ok 98345 numbers

Test #34:

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

input:

81509 65745 92452
49354 34810
8622 33343
50412 37468
49936 15350
28400 76011
5783 77041
61734 75149
67014 22641
4383 53957
28387 47981
31116 29067
75760 43023
23755 42103
47843 18332
62808 52998
5475 54810
28429 30311
66710 41985
27014 941
22865 26848
23077 70957
63837 44035
76582 15522
34929 56916
...

output:

1
288657830
0
36
0
823382229
18
900209101
1
1
9
863473482
5
10
13
-1
-1
18
5
-1
19
191045131
-1
338788091
515754535
10
7
153076941
9
9
-1
-1
624159177
22
447801526
0
-1
16
7
23
18
0
5
-1
8
205178734
460106421
11
-1
4
9
-1
-1
40
11
31
25134523
0
893910365
-1
22
974842053
255419268
-1
110475679
4
3245...

result:

ok 92452 numbers

Test #35:

score: 0
Accepted
time: 129ms
memory: 65396kb

input:

86062 62587 67898
43480 83208
17379 22207
47108 68751
22580 39089
3008 82506
49192 60834
10310 6575
66846 63674
5682 25660
51189 28041
26228 5426
68976 82407
4677 79283
54670 42025
1329 24852
26404 8250
55952 80318
82793 73010
23357 25720
15807 27501
56833 36734
54028 4776
30141 62606
16914 73748
17...

output:

5
-1
12
596750411
13
2
9
7
783444497
878815469
-1
-1
1
2
12
249233158
-1
-1
5
802152487
277062422
12
-1
300049910
517386857
194834234
77763097
18
0
250996222
-1
8
4
257017672
431764689
-1
15
-1
20
14
8
7
5
11
-1
829219569
13
-1
20
9
515068453
17
844263421
-1
-1
2
208141009
-1
2
51071435
-1
223646633...

result:

ok 67898 numbers

Test #36:

score: 0
Accepted
time: 134ms
memory: 71048kb

input:

85597 67904 62108
60297 28397
71504 61404
22457 28947
44913 10671
65193 69263
24502 50423
65517 10490
16524 42170
62530 78419
46462 1393
57056 79601
13548 40280
48183 23818
12286 2477
38480 27165
39755 75770
80398 30025
56184 7559
28443 2221
38668 80752
37882 76381
27582 68267
26826 25574
20061 6754...

output:

20
-1
9
500482074
-1
851726926
-1
-1
25
-1
707882955
22
960435558
-1
3
-1
12
9
-1
7
11
39
15
54408381
701139919
8
14
21
755889642
13
-1
0
829903105
230747519
353085370
1
17
437594825
-1
2
17
650727093
328332802
4
37
28
19
824019553
23
21
7
22
24
925714614
23
9
16
5
-1
21
20
21
25
-1
306032242
26
4
5...

result:

ok 62108 numbers

Test #37:

score: 0
Accepted
time: 205ms
memory: 95276kb

input:

100000 100000 100000
59460 31535
38066 37341
11080 298
2860 17409
60825 21380
83605 34555
62083 1718
80719 85245
10907 87649
97190 27952
57980 6051
47176 46181
25905 51438
85582 98980
2604 29374
9368 74079
19512 91742
56200 49805
192 33397
71598 97429
88536 39765
85497 88273
8704 27196
31447 15732
5...

output:

-1
23
0
2
-1
1
18
41
17
23
7
-1
-1
43
19
-1
24
2
5
16
6
-1
21
21
0
35
-1
0
10
-1
-1
14
-1
19
29
-1
34
6
9
35
-1
3
-1
2
-1
-1
-1
5
33
35
25
12
8
3
0
-1
1
3
8
7
0
-1
3
7
-1
4
5
27
31
0
22
0
12
12
9
9
-1
27
16
-1
-1
-1
22
-1
-1
13
20
19
0
1
13
25
-1
0
0
4
34
17
21
13
1
-1
16
14
24
17
6
4
0
19
-1
15
14
...

result:

ok 100000 numbers

Test #38:

score: 0
Accepted
time: 193ms
memory: 92616kb

input:

100000 100000 100000
36402 64516
94719 61008
16369 49712
52690 71424
53375 27051
23745 40264
67125 6053
16867 89755
21609 98203
83462 8013
33383 10876
48749 60616
55222 15130
69719 47126
37792 34214
47702 68605
10894 6922
71888 64696
67366 50200
17839 94366
77796 45773
7930 7649
15943 34723
27458 94...

output:

-1
-1
2
15
24
-1
13
-1
1
17
-1
12
24
23
10
26
-1
7
34
-1
-1
7
25
18
5
-1
1
-1
1
-1
-1
-1
24
14
6
28
36
14
19
18
20
27
1
-1
2
-1
7
6
21
-1
19
-1
19
5
13
-1
6
-1
14
19
8
28
26
-1
13
5
15
-1
9
16
-1
24
-1
7
42
26
4
1
-1
22
18
5
4
21
3
3
7
9
26
22
11
5
19
-1
8
10
2
5
15
8
6
29
14
8
8
18
7
10
11
4
32
47
...

result:

ok 100000 numbers

Test #39:

score: 0
Accepted
time: 203ms
memory: 95436kb

input:

100000 100000 100000
82030 2978
92364 827
43402 87675
26896 19682
34658 78765
23623 24095
9936 89310
24324 48292
37636 73148
88631 83139
3676 60900
37446 12820
53353 43555
21857 12279
60922 68095
47891 2130
67461 89205
34120 1740
14774 96621
35080 35682
42858 70329
40981 64931
1241 8802
95621 92547
...

output:

27
22
2
34
2
-1
35
-1
26
-1
5
28
12
-1
6
-1
-1
21
-1
9
-1
17
19
29
8
7
-1
39
16
7
19
-1
5
20
21
13
18
31
3
29
46
10
10
11
-1
12
35
-1
20
-1
9
-1
28
-1
9
-1
-1
3
4
5
23
-1
15
11
12
-1
23
3
-1
5
-1
-1
-1
40
21
-1
6
18
7
15
24
40
0
-1
2
35
4
12
11
5
0
15
-1
12
31
23
3
40
0
-1
10
21
0
17
6
28
5
38
20
-1...

result:

ok 100000 numbers

Test #40:

score: 0
Accepted
time: 182ms
memory: 95668kb

input:

100000 100000 100000
11986 83456
739 15906
93410 59302
91059 88051
39176 73486
40225 20556
29101 8590
76649 40318
91428 43712
90226 20173
16520 1171
31972 61893
56824 1701
49324 12586
90856 12480
58505 53126
28886 92352
61629 74710
86706 46467
96490 65373
83448 30792
52836 37748
91466 58601
66245 89...

output:

-1
-1
-1
31
-1
28
51
4
6
-1
21
24
25
3
-1
16
21
18
25
16
0
-1
30
26
42
12
-1
38
23
17
12
18
28
5
17
4
7
3
-1
-1
-1
-1
13
36
12
23
12
10
-1
19
-1
10
11
20
27
13
15
0
4
12
9
-1
-1
13
13
5
2
46
21
-1
-1
-1
14
-1
18
4
44
3
3
-1
13
17
-1
-1
-1
11
18
15
21
44
12
9
-1
-1
18
9
28
4
8
24
4
-1
10
19
0
25
28
2...

result:

ok 100000 numbers

Test #41:

score: 0
Accepted
time: 175ms
memory: 95212kb

input:

100000 100000 100000
37314 75554
56570 49497
61657 61370
69426 47265
87607 41319
96227 35135
44458 6184
99398 32909
22600 75816
46160 69796
83731 62973
76829 46598
54708 64172
60832 22845
94634 97056
47845 26891
79190 81215
18696 21581
88160 27317
65286 20011
81725 41951
15797 15675
87491 53495
1408...

output:

13
28
13
12
-1
19
-1
42
17
-1
6
21
-1
14
8
26
7
13
-1
36
8
-1
36
27
39
28
13
15
24
8
0
-1
-1
-1
17
28
29
28
-1
24
-1
18
18
18
17
35
-1
7
46
34
-1
-1
-1
2
13
9
-1
9
3
-1
-1
8
26
5
-1
2
19
15
-1
28
45
32
-1
46
11
-1
48
10
13
10
32
30
1
14
27
-1
0
14
15
0
10
8
16
-1
-1
-1
-1
3
14
9
28
14
26
30
-1
10
14...

result:

ok 100000 numbers

Test #42:

score: 0
Accepted
time: 248ms
memory: 102084kb

input:

100000 100000 100000
76068 7296
41396 45021
73566 99899
75813 64808
98511 72613
31578 53731
12961 43423
39676 5383
51240 14929
76865 75571
40210 96614
64178 70547
71018 52102
67542 8034
18832 92799
48499 74483
97652 8824
78096 95966
45473 39796
41469 49479
99942 61045
23638 27349
54318 94950
63441 7...

output:

2658
39788
-1
10555
11145
1758
7234
65388
917
16004
-1
-1
69019
21322
-1
-1
-1
7232
45804
13701
25693
31840
39739
7675
-1
18467
57520
-1
-1
3126
59223
-1
20687
-1
6237
-1
-1
-1
-1
-1
24398
85103
63766
22465
11066
80911
27286
10543
577
6152
1371
913
5671
14985
-1
1254
45506
105956
67364
57220
40562
-...

result:

ok 100000 numbers

Test #43:

score: 0
Accepted
time: 234ms
memory: 102604kb

input:

100000 100000 100000
9734 92605
38258 84722
97136 27157
80949 45066
36421 60692
11650 67903
53840 15913
58808 48958
29183 5907
91508 96918
89419 47264
96660 92790
63658 9998
93566 76149
93573 69576
33014 31010
42303 55655
91956 97775
88846 30844
52540 1779
42488 13686
3488 18873
8342 75843
44845 358...

output:

-1
37094
66970
31736
1999
52078
-1
26276
-1
896
37011
10735
214
284
6005
17133
-1
14675
4502
34876
29557
12383
-1
17364
7943
16368
-1
791
42816
16399
-1
13347
2179
10729
62246
1837
37376
-1
873
27262
-1
1207
18308
70855
10416
5700
43185
5473
21679
6787
34130
221
-1
30281
34117
21362
5405
30524
-1
-1...

result:

ok 100000 numbers

Test #44:

score: 0
Accepted
time: 232ms
memory: 101888kb

input:

100000 100000 100000
40662 71787
70900 1201
99487 14610
20602 48067
41195 75859
33402 38996
62411 5089
51703 62936
89414 58564
8768 66908
37846 11656
25714 35770
23034 74795
94481 96979
46136 42233
47147 350
96174 38939
56155 11051
87057 11399
24031 71434
96293 60198
60505 1497
90332 31561
93733 263...

output:

57352
38558
94
35261
-1
26773
21993
41944
7662
-1
751
-1
9407
21383
-1
23989
508
-1
18414
-1
29263
-1
21176
76798
5431
2358
-1
637
77230
-1
42010
14837
23671
12809
-1
1199
-1
5387
1564
8336
9289
11494
17118
2010
14008
7681
43358
-1
6820
-1
8603
27415
2621
2277
2927
5971
18333
-1
-1
57991
21716
-1
82...

result:

ok 100000 numbers

Test #45:

score: 0
Accepted
time: 234ms
memory: 95808kb

input:

100000 100000 100000
3761 68170
9321 15027
28373 96782
76980 83446
89745 18468
36043 76769
67550 66797
42666 51740
64043 90413
69555 39277
5786 18353
31271 32540
31765 9310
32663 58143
68467 31687
5161 49139
14487 58297
42106 83006
82994 35852
50310 54265
38631 86657
89078 16218
6446 52044
45204 359...

output:

829
477
-1
219
644
666
-1
-1
682
356
-1
-1
94
1042
-1
1267
662
899
706
-1
-1
-1
-1
789
-1
-1
230
416
530
474
208
855
-1
556
158
531
133
332
-1
201
-1
252
399
801
-1
-1
-1
-1
115
1186
422
2036
1079
57
1355
429
940
-1
983
1038
323
-1
3415
279
54
525
423
1182
286
-1
617
61
47
-1
662
12
209
1003
1172
68...

result:

ok 100000 numbers

Test #46:

score: 0
Accepted
time: 210ms
memory: 95132kb

input:

100000 100000 100000
58736 22267
65164 27968
24172 96971
83102 91482
51804 45314
61977 55314
98623 32309
80645 464
1295 82720
26604 11856
66619 20080
54006 50587
18582 24696
62561 70733
1158 70320
59782 39247
38619 31137
42230 59864
77951 46302
24152 58718
28965 228
59700 67060
83693 46387
72431 618...

output:

816
294
-1
1410
1888
1077
1291
1312
1775
587
608
200
1389
473
1806
295
-1
647
-1
-1
-1
19
1370
50
-1
176
519
695
1275
1635
73
389
1158
1469
-1
316
1807
693
1639
64
310
779
743
-1
-1
-1
-1
-1
-1
-1
-1
436
393
319
587
1266
-1
721
387
873
1087
1033
312
243
915
528
-1
1282
-1
-1
-1
154
969
1288
-1
-1
23...

result:

ok 100000 numbers

Test #47:

score: 0
Accepted
time: 203ms
memory: 95548kb

input:

100000 100000 100000
78419 49272
48863 97407
72067 83599
96225 1441
90643 9454
62852 97288
20748 10977
74695 76622
81297 43934
5691 64248
53900 98275
13923 78963
54576 40332
10419 20021
88203 68665
25457 79326
22625 62863
10278 52862
39012 22041
8139 69654
47389 16503
72095 96706
92793 86572
43317 9...

output:

1601
1216
-1
61
-1
-1
734
28
-1
1582
-1
2280
1451
1825
3089
-1
109
1402
-1
-1
117
2001
1374
-1
978
723
958
-1
-1
40
285
657
468
-1
1806
428
-1
123
-1
674
825
-1
1580
1269
57
-1
955
587
-1
1785
1710
405
640
267
-1
1381
2953
861
-1
1349
1815
783
41
1564
1419
-1
596
2571
638
-1
-1
-1
695
935
673
1295
2...

result:

ok 100000 numbers

Test #48:

score: 0
Accepted
time: 156ms
memory: 94944kb

input:

100000 100000 100000
50697 5296
59976 50697
34399 50697
50697 94024
50697 26795
50697 14759
1408 50697
50697 69493
50697 49674
50697 17610
38774 50697
50697 62735
50697 454
50697 47506
50697 72137
50697 62882
49963 50697
79375 50697
5920 50697
50697 51185
50697 79001
41597 50697
82801 50697
50697 54...

output:

0
1
0
-1
-1
2
1
0
0
2
0
-1
-1
1
0
0
0
1
0
0
2
0
-1
-1
0
5
0
-1
-1
3
1
4
0
3
-1
0
-1
-1
2
1
11
2
2
1
0
-1
-1
2
-1
-1
1
0
2
0
1
0
0
0
2
1
1
-1
1
-1
0
4
5
0
1
0
1
4
-1
0
1
4
3
1
-1
-1
0
-1
2
2
3
-1
0
-1
0
-1
-1
0
0
-1
-1
1
-1
1
4
3
4
-1
-1
-1
0
2
-1
3
3
0
-1
2
-1
-1
2
0
0
4
0
3
3
1
1
0
-1
-1
-1
1
-1
2
...

result:

ok 100000 numbers

Test #49:

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

input:

100000 100000 100000
35433 98292
98292 79665
32969 98292
98292 11670
98292 49554
60998 98292
98292 12199
52764 98292
82071 98292
73612 98292
23530 98292
49183 98292
98292 22743
98292 4732
57883 98292
15025 98292
98292 47750
98292 78202
98292 64713
98292 8755
85122 98292
98292 27812
98292 32766
65671...

output:

4
2
5
-1
-1
2
0
2
1
-1
0
0
0
2
0
1
1
0
1
0
-1
-1
-1
0
2
3
0
1
0
6
0
0
-1
3
0
-1
0
0
0
0
2
-1
0
3
-1
4
-1
0
2
1
0
1
0
-1
0
0
1
1
1
1
4
0
1
1
0
4
1
0
0
4
0
2
2
0
-1
-1
3
-1
4
1
0
1
1
0
3
2
1
0
-1
1
0
0
1
3
3
1
0
0
-1
1
2
0
0
-1
1
2
0
-1
0
-1
0
0
1
1
2
0
2
1
2
2
0
0
0
1
1
-1
-1
-1
0
0
2
1
0
-1
1
-1
1
1...

result:

ok 100000 numbers

Test #50:

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

input:

100000 100000 100000
44049 78136
88151 44049
23888 44049
44049 43223
43186 44049
43619 44049
47209 44049
44049 91286
20545 44049
44049 68319
44049 95688
44049 93786
44049 51527
44049 29972
44049 54200
34186 44049
49268 44049
44049 78728
44049 46959
83873 44049
44049 7154
24505 44049
35269 44049
3490...

output:

0
-1
4
2
2
2
0
-1
3
0
0
0
-1
0
-1
2
1
0
-1
2
0
3
2
-1
-1
2
0
3
0
1
3
1
0
0
-1
4
0
0
1
0
1
-1
-1
0
1
2
0
0
0
2
4
3
-1
0
-1
0
-1
-1
-1
-1
-1
0
0
-1
1
-1
1
-1
0
0
2
0
0
0
3
4
-1
0
1
5
2
0
2
1
0
0
-1
1
2
-1
2
0
-1
1
0
3
-1
3
1
1
1
1
0
0
0
-1
2
0
1
2
-1
4
-1
6
-1
-1
0
0
2
-1
0
1
-1
1
0
-1
1
5
3
2
1
1
1
1...

result:

ok 100000 numbers

Test #51:

score: 0
Accepted
time: 134ms
memory: 95760kb

input:

100000 100000 100000
97815 97148
42716 97815
70038 97815
24575 97815
97815 44412
97815 34088
97815 40920
97815 63152
97815 2103
97815 83246
16688 97815
97815 50219
50087 97815
97815 56044
97815 2521
97815 4673
97815 85239
97815 63341
798 97815
97815 59521
7676 97815
50664 97815
86193 97815
97815 542...

output:

1
0
1
-1
0
0
0
2
0
0
4
1
2
0
3
-1
-1
-1
0
0
1
0
-1
-1
1
5
1
-1
0
3
5
0
-1
1
1
2
5
4
0
1
0
1
1
2
0
-1
-1
4
1
2
0
0
1
0
-1
0
3
2
1
-1
0
-1
-1
2
-1
-1
1
-1
0
0
0
0
-1
-1
-1
1
1
0
3
-1
1
0
1
0
-1
0
-1
0
5
-1
-1
-1
-1
4
8
1
0
-1
1
2
2
-1
0
1
0
1
2
-1
0
0
1
-1
-1
3
0
2
0
2
0
7
1
-1
-1
0
0
0
2
0
1
1
0
1
3
...

result:

ok 100000 numbers

Test #52:

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

input:

100000 100000 100000
44721 51187
20304 80798
29792 7839
82677 19253
35408 14929
94348 87779
46456 53826
26842 89974
53744 13031
60616 70413
43077 97598
84385 22213
14562 84272
38031 88639
46734 2889
54309 40637
93364 79789
93999 80276
69038 96370
73537 5026
47462 65537
20966 78739
24122 24377
95732 ...

output:

-1
4
-1
36441
-1
2570
-1
23273
3
-1
-1
-1
10
24
63633
42745
34938
49953
-1
67004
5899
67151
3
1
83414
-1
4454
5
-1
23096
65288
-1
-1
64391
41815
47481
82601
36954
-1
63760
31870
1678
4
12
8
-1
6
7240
-1
2
-1
30151
5
1
2
6
-1
-1
1
7
41873
5
-1
-1
42387
-1
54442
13
38890
38280
1421
-1
53095
5
9
11
12
...

result:

ok 100000 numbers

Test #53:

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

input:

100000 100000 100000
54266 37133
72890 56290
5796 62431
5424 35134
97945 9095
89540 87022
53040 79848
12938 1337
39680 25346
12266 64387
65110 13425
97677 86175
44418 12122
38479 18533
94344 94036
89410 60789
46760 74500
86208 56297
78731 35073
84455 10500
56711 42883
35058 7751
22970 70698
8004 671...

output:

21
1
36762
29776
73141
40489
4
44190
-1
1
66595
10427
6
10207
24180
-1
3
49679
23
19
-1
-1
4
0
2
20
49118
36391
14828
42209
39119
8
16772
-1
-1
12
-1
9
-1
14513
51017
-1
27
-1
45520
28189
-1
54519
5489
2
66184
-1
-1
0
-1
24713
13
10
6
25545
-1
21455
10
56375
61517
-1
-1
54854
18
0
31
9
29
23
3
12
0
...

result:

ok 100000 numbers

Test #54:

score: 0
Accepted
time: 168ms
memory: 94400kb

input:

100000 100000 100000
59723 16175
5063 5463
37269 90647
52774 98634
76226 42963
905 70473
50625 11410
93189 93554
47976 72059
32917 73782
17160 49210
66287 13481
80778 7278
5044 85286
63832 2527
37655 81052
60247 22956
15792 41621
66646 56396
26933 30865
97952 55227
43654 14041
85028 97726
77518 5036...

output:

8
77533
-1
-1
73824
0
12
-1
-1
10691
91707
3
64669
3
-1
-1
59735
2
63432
3
-1
-1
2
5
281
8024
33735
56425
19993
32694
2
0
84658
-1
-1
19334
5
75452
42679
2883
25021
64984
-1
10
15386
-1
5
11
4
-1
45820
3
42954
55439
-1
1
7
-1
4
-1
6
1
-1
5
52025
1
7
74726
10850
12
13
35148
1
88868
-1
49551
4
3
-1
-1...

result:

ok 100000 numbers

Test #55:

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

input:

100000 100000 100000
77106 17554
79186 15500
96515 7383
89166 58158
51812 54082
86382 93130
11024 1070
2804 85021
69213 93541
95849 33909
21258 93059
81340 73510
82500 97672
7324 71381
12525 83406
21315 50824
51872 50340
69459 45865
4888 22648
58792 736
14920 28735
12151 30606
62258 75174
90675 3606...

output:

-1
25
35
-1
-1
10
19
-1
10
-1
19
17
-1
9
16
12
-1
9
-1
16
-1
-1
11
28
1
18
22
8
0
-1
31
20
18
14
15
-1
3
21
4
29
37
18
3
20
41
1
-1
16
-1
-1
33
20
-1
13
14
16
-1
-1
-1
35
40
32
5
5
9
19
22
10
14
8
28
-1
-1
26
29
21
-1
39
-1
3
0
14
-1
9
15
1
31
2
32
-1
13
18
10
6
3
12
-1
-1
12
37
34
1
14
3
7
25
-1
14...

result:

ok 100000 numbers

Test #56:

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

input:

100000 100000 100000
82120 62689
8686 91188
86132 29983
28392 96925
13238 41513
31260 98446
30183 86516
38915 22671
47467 35924
27883 58187
47910 44477
16321 53199
48984 11873
5814 32753
66731 18405
86499 73623
66650 7906
50312 86451
86551 41981
52719 36414
18302 26734
65072 44291
66665 43916
13400 ...

output:

9
13
2
2
1
4
1
0
3
4
3
-1
5
0
8
7
9
-1
6
-1
-1
3
0
-1
10
0
-1
9
-1
-1
-1
3
-1
12
-1
12
2
-1
-1
10
-1
7
3
0
-1
5
3
8
6
9
-1
5
-1
15
-1
3
4
9
7
5
10
3
-1
3
7
13
-1
5
1
2
2
-1
6
-1
0
-1
-1
8
7
11
7
-1
-1
11
1
5
5
12
-1
15
-1
-1
-1
6
8
-1
4
-1
1
5
2
2
14
1
5
5
-1
0
-1
14
-1
14
13
13
1
9
2
10
-1
7
0
-1
9...

result:

ok 100000 numbers

Test #57:

score: 0
Accepted
time: 134ms
memory: 96344kb

input:

100000 100000 100000
87464 87051
97506 12023
34712 79829
35781 88444
96920 86649
95453 84284
87439 34898
48143 70845
96141 61423
15999 38361
96488 13323
44851 64700
91140 65054
79922 72775
89340 60716
34205 78131
9180 64417
83359 47822
52041 54587
51644 8676
13124 20588
36069 42192
65316 99897
38711...

output:

22
29
4
16
3
24
22
20
23
-1
35
-1
25
37
19
-1
11
-1
26
-1
17
4
15
-1
8
26
23
7
25
-1
45
17
-1
-1
27
29
21
19
31
-1
-1
29
-1
17
41
-1
43
13
41
13
12
26
12
14
23
-1
9
-1
4
-1
12
18
34
22
-1
23
32
0
0
33
-1
38
13
29
-1
16
-1
17
-1
-1
46
22
-1
6
31
39
-1
22
9
6
-1
16
-1
-1
7
7
30
33
-1
-1
26
-1
12
18
29...

result:

ok 100000 numbers

Test #58:

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

input:

100000 100000 100000
11234 56294
177 92557
8602 71052
75272 88166
61119 32927
71724 70986
16297 22157
96846 76128
99220 18399
92582 49749
47553 83201
98839 73757
78233 87507
33650 54615
29145 77245
87510 27489
27372 48882
10759 25457
18069 36471
55011 45063
594 45481
14896 85532
41187 89023
38416 30...

output:

9
3
26
13
7
11
37
8
9
8
29
-1
6
15
31
-1
13
33
39
23
21
21
29
23
25
-1
27
-1
24
22
19
3
22
6
2
-1
13
5
-1
7
13
32
26
-1
9
21
28
43
13
-1
15
-1
-1
17
9
17
-1
0
-1
21
18
-1
12
29
1
19
19
26
36
5
10
39
36
7
31
27
16
43
23
6
29
7
20
34
26
24
47
15
44
17
6
-1
42
11
28
21
39
6
6
23
13
-1
12
23
28
7
-1
26
...

result:

ok 100000 numbers

Subtask #3:

score: 30
Accepted

Test #59:

score: 30
Accepted
time: 180ms
memory: 77312kb

input:

95629 64841 64314
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51...

output:

-1
701714740
-1
610354140
816755067
2440
245932872
-1
29509
866966613
744072492
890
-1
969398264
588051152
381506396
2347
5427
4829
44377
195466300
60823
508
459304253
400544113
-1
787773518
3856
9692
6576
322820913
900985028
1473
14691
26175
-1
27082
-1
9735
3846
537036842
-1
261459575
86658
635912...

result:

ok 64314 numbers

Test #60:

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

input:

92502 51399 68929
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51...

output:

36266
-1
-1
112572200
27068354
-1
10394
329233107
444229297
223185833
363055390
1754
14433
-1
4346
-1
33082
457460095
-1
5482
749013593
717085104
5006
-1
926464006
1983
589805099
7590
264497528
8979
903766762
24704
903
923960764
4211
53272133
17012
435443676
-1
984123705
-1
1980
-1
2907
20373
813690...

result:

ok 68929 numbers

Test #61:

score: 0
Accepted
time: 216ms
memory: 88528kb

input:

53810 92751 89379
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51...

output:

462043454
6397
31647
98446547
81496
14
34784
1587
532169187
35742
753712897
400460299
299860851
-1
26049
984595650
8185
13794
721579357
166901630
16093
-1
48327
52280
-1
36956
49549
33065
703982006
15511
171757272
130683368
-1
16949
-1
96442497
948433381
-1
-1
-1
3
55603
-1
120939988
12974
952750599...

result:

ok 89379 numbers

Test #62:

score: 0
Accepted
time: 313ms
memory: 102900kb

input:

100000 100000 100000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50...

output:

22357
29573
45104
2184
-1
109258
31337
-1
26387
41578
8392
36172
1160
9470
-1
6923
-1
-1
302
26401
-1
52971
25666
1970
104774
-1
33764
-1
-1
43624
5470
26387
38352
-1
8495
8983
7396
8448
4711
72385
-1
4832
-1
5388
4583
1151
38790
30979
-1
17732
28535
45088
-1
-1
97310
15663
92961
12755
949
-1
22729
...

result:

ok 100000 numbers

Test #63:

score: 0
Accepted
time: 344ms
memory: 102468kb

input:

100000 100000 100000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50...

output:

6483
8781
-1
24456
222
-1
12374
98
41520
29393
-1
12028
17768
6307
74435
24594
11204
16315
48834
4474
4600
27773
-1
60970
14035
-1
-1
24779
-1
43438
18890
33556
-1
12374
-1
94129
30482
14337
40498
-1
57947
-1
44294
49557
-1
-1
9235
9347
-1
38102
23295
102062
10387
-1
25191
107152
7034
71071
-1
-1
-1...

result:

ok 100000 numbers

Test #64:

score: 0
Accepted
time: 348ms
memory: 102460kb

input:

100000 100000 100000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50...

output:

6354
42704
101441
2857
-1
5542
731
16360
9695
3884
-1
27833
3621
2789
57396
17523
-1
-1
44325
575
7390
-1
-1
39509
17011
27425
-1
12285
62336
-1
-1
-1
-1
3146
273
25050
37917
50109
35442
31916
3096
47751
65204
-1
34032
39181
-1
27586
-1
30894
-1
-1
24707
2796
18515
45391
99909
15335
10383
10905
-1
3...

result:

ok 100000 numbers

Test #65:

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

input:

100000 100000 100000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50...

output:

2311
-1
24585
99022
24662
57394
69711
535
27286
32344
2731
9879
-1
27909
49883
1296
14120
40331
40056
-1
-1
12185
19154
16114
-1
277
23779
-1
-1
13181
52941
31439
10184
-1
3425
5039
-1
80057
-1
253
2188
89575
6499
-1
21752
75653
-1
56204
-1
25131
-1
47353
-1
3783
-1
25426
33521
-1
44916
15271
3317
1...

result:

ok 100000 numbers

Test #66:

score: 0
Accepted
time: 234ms
memory: 103404kb

input:

100000 100000 100000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50...

output:

2587
12143
16964
21386
-1
101210
-1
6285
2557
13670
20738
43749
919
53823
4494
98909
-1
65499
670
-1
21401
2009
66503
-1
-1
49535
62266
37556
6535
731
-1
111804
4842
3527
3557
1260
30321
68998
57960
11241
26780
2411
74629
60899
92019
73225
9479
-1
13551
2534
1509
13677
3454
113005
11
-1
3573
9791
-1...

result:

ok 100000 numbers

Test #67:

score: 0
Accepted
time: 227ms
memory: 103204kb

input:

100000 100000 100000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50...

output:

77660
52
106332
14061
3270
105
18174
-1
77805
50254
969
2318
4576
4994
31416
-1
12558
24255
6163
112456
-1
3285
65589
1757
18715
8429
-1
12879
25335
21564
85094
800
-1
6169
7190
696
7335
5834
11350
58406
-1
49158
39385
45499
-1
22975
-1
18130
103
50778
15483
23138
10195
1015
2379
-1
-1
-1
100907
-1
...

result:

ok 100000 numbers

Test #68:

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

input:

100000 100000 100000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50...

output:

8988
-1
14443
-1
9877
566
9580
29456
4906
1691
2002
-1
11435
16258
6720
25040
3685
10643
13471
-1
-1
2122
20594
21629
-1
2249
-1
7575
-1
26840
3457
-1
16212
27410
-1
12628
735
35566
9707
33849
-1
-1
14253
7281
-1
29983
22468
17260
-1
26884
32563
5205
32034
18537
-1
23089
-1
-1
20489
16040
-1
14918
3...

result:

ok 100000 numbers

Test #69:

score: 0
Accepted
time: 159ms
memory: 102824kb

input:

100000 100000 100000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50...

output:

1742
787
2082
1836
-1
-1
1627
5815
-1
4401
4394
3625
1587
-1
-1
-1
4148
-1
-1
8136
6572
5217
1943
2258
-1
3108
3768
4306
-1
4910
-1
133
4849
-1
5841
3316
1800
960
1422
-1
-1
1551
2020
6543
5501
1369
969
2603
7944
-1
1593
2764
1249
-1
3673
2691
2441
-1
-1
525
6117
6052
-1
7356
1396
319
1791
3598
5547...

result:

ok 100000 numbers

Test #70:

score: 0
Accepted
time: 202ms
memory: 102340kb

input:

100000 100000 100000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50...

output:

18837
23143
-1
8074
17906
23043
22447
4474
-1
-1
-1
23669
18990
8666
30486
13797
15263
7816
37953
8640
11509
-1
-1
29212
-1
18317
11521
1666
35408
-1
40547
15656
36307
-1
32990
44551
-1
-1
982
22202
-1
25209
-1
14796
687
3218
30059
2421
6558
7656
2579
-1
-1
-1
46022
-1
18254
38968
24549
19782
-1
144...

result:

ok 100000 numbers

Test #71:

score: 0
Accepted
time: 207ms
memory: 102552kb

input:

100000 100000 100000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50...

output:

17013
-1
41429
-1
9558
14122
4177
2863
6179
10012
18668
-1
22362
-1
7604
1525
-1
1695
21676
9201
14992
11539
13085
5285
125129
9680
7725
-1
2697
7054
-1
-1
12370
2872
14385
-1
11028
-1
4915
10533
19472
8246
-1
19183
-1
8850
-1
9950
-1
-1
12145
3988
4652
8232
-1
1884
63752
-1
18594
14048
9432
1651
79...

result:

ok 100000 numbers

Subtask #4:

score: 32
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #72:

score: 32
Accepted
time: 130ms
memory: 88988kb

input:

83066 93318 63959
18587 12118
20710 13393
24657 64380
45691 2239
77997 64239
27268 14508
7050 67455
78465 18480
36411 63396
2387 70161
66041 62352
36605 57150
62413 78314
69932 20048
75256 47446
51733 18435
60170 13084
46841 1577
32875 15320
10381 40963
22700 18417
46204 34274
30659 76209
69447 6795...

output:

9
-1
4
13
998074065
22
371026618
108534236
12
-1
7
261270855
22
22
36
11
5
30
893476801
732617386
836403074
0
-1
-1
26
42
215182423
16
485732041
265677463
22
23
0
19
36
-1
-1
-1
182996094
5
7
15
4
21
11
56
-1
17
19
589988270
23
8
127377069
23
918888954
676971191
23
-1
26
31
-1
7
29
19
22
10
13
4
141...

result:

ok 63959 numbers

Test #73:

score: 0
Accepted
time: 120ms
memory: 78984kb

input:

53279 84732 77236
37399 9659
15186 45676
14060 9086
5847 39279
12718 30679
8499 49435
13410 21563
17294 33443
22832 9398
17273 30187
25069 20801
42959 12195
26974 29577
44990 3478
13607 40163
805 37696
14834 44488
41769 17809
44908 49540
17730 42514
27760 33266
16930 13514
14851 42250
40474 42395
40...

output:

14
-1
858027541
-1
12
18
-1
28
30
29472505
1
35
47
8
14
31
53
19
843763372
30
56
747541305
852529135
-1
17
328565010
642975065
52
24
178294074
49
585349570
831135704
386028201
867020667
-1
12
20
40
9
997756399
-1
33
-1
8
2
18
791198622
6
442105585
760447184
29
21
10
194362983
127381695
4
1
34
597738...

result:

ok 77236 numbers

Test #74:

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

input:

52299 58628 79622
49472 50205
52187 1044
29889 18376
3013 14429
32378 48769
14649 50835
49235 41762
13274 51549
12380 39699
47182 50765
23733 27404
8870 38092
5428 22576
46669 2552
31266 26904
40023 28377
29041 37126
36160 40440
13146 17595
25114 13178
38798 17382
43630 39852
32459 26215
31453 44521...

output:

-1
23
2
3
31
22
0
30
22
56199921
30
783761725
17
24775948
10
32
19
-1
-1
41
31
14
-1
16
4
19
62619873
10
33
1
332357707
804481300
922967205
935965661
455133927
-1
24
532780131
46
8
-1
12
29
663280931
40
29
27
33
17
-1
813105385
-1
8
31
267842838
672238233
23
20
-1
31
3
7
819764
22
2
-1
27
3
24639230...

result:

ok 79622 numbers

Test #75:

score: 0
Accepted
time: 212ms
memory: 95716kb

input:

100000 100000 100000
95163 36299
13428 67931
939 89504
63640 84486
82410 79507
47435 92345
17958 71031
43929 540
68970 6904
99289 50916
35242 2162
27740 91360
70708 42035
80629 32967
28540 941
87401 33847
81039 56750
12208 81239
87719 91017
66976 23387
67409 48712
60426 4626
68 46448
67155 39601
370...

output:

13
27
19
20
14
29
-1
2
22
-1
11
1
16
4
-1
-1
12
35
-1
15
-1
-1
20
3
-1
26
2
1
-1
21
6
21
21
-1
-1
16
5
7
26
6
27
9
13
3
2
-1
-1
-1
1
19
21
3
-1
11
-1
-1
14
14
-1
5
-1
15
9
-1
11
4
15
6
32
0
1
21
11
21
9
15
-1
28
9
-1
10
41
-1
-1
-1
21
-1
8
23
6
-1
1
-1
32
-1
-1
-1
10
32
9
-1
13
-1
-1
35
-1
14
9
-1
5...

result:

ok 100000 numbers

Test #76:

score: 0
Accepted
time: 204ms
memory: 95496kb

input:

100000 100000 100000
90895 78085
97088 63552
37051 11689
52025 61776
96347 8426
99365 53460
54937 18891
60103 92049
53352 62458
19083 77735
47538 44280
81001 93026
43417 16030
49652 22785
48587 86035
70351 91635
5747 90246
71265 30181
83343 15789
96652 22702
47494 3228
15173 70990
54008 28811
35737 ...

output:

-1
1
-1
22
26
-1
-1
22
7
12
26
51
17
12
-1
25
-1
24
2
29
10
37
19
7
-1
20
1
3
-1
5
9
11
-1
12
-1
9
-1
10
13
16
-1
18
15
-1
10
-1
2
38
5
-1
-1
2
-1
-1
33
24
-1
11
2
-1
11
33
19
-1
5
8
4
-1
-1
-1
-1
-1
16
35
-1
-1
24
-1
14
-1
22
15
-1
25
15
22
-1
10
24
20
18
1
4
21
9
-1
27
-1
23
-1
23
26
13
28
17
13
1...

result:

ok 100000 numbers

Test #77:

score: 0
Accepted
time: 182ms
memory: 94424kb

input:

100000 100000 100000
31215 5995
67876 38095
64743 89784
8680 76173
19040 10996
10514 55427
40632 74497
96143 91367
30954 95569
51752 32186
35808 54206
28355 4277
16090 33960
31767 57517
32261 5781
65477 86959
32834 18760
96337 38322
65459 6049
80146 65146
78861 33376
43571 74333
58827 93835
33240 60...

output:

16
18
3
5
6
9
12
12
31
16
-1
7
19
23
46
27
12
11
2
12
-1
22
25
-1
14
-1
-1
-1
-1
21
-1
3
29
-1
4
3
11
2
8
20
-1
-1
3
60
16
-1
-1
6
38
1
19
8
19
6
8
3
-1
27
10
14
23
19
-1
33
12
34
-1
0
12
-1
11
17
15
19
11
-1
29
23
-1
11
-1
37
31
-1
5
-1
29
-1
13
20
5
0
-1
-1
-1
26
14
25
5
-1
1
11
-1
3
-1
4
2
8
3
24...

result:

ok 100000 numbers

Test #78:

score: 0
Accepted
time: 172ms
memory: 94608kb

input:

100000 100000 100000
95662 11069
82098 37807
33353 69085
72776 23095
1925 73567
78780 91062
72066 20942
37357 3678
38970 47701
3457 76743
25953 19457
65247 80364
65311 96897
18147 24089
89255 69845
81219 32684
98423 68755
58157 11773
22395 9584
18753 9430
54832 33669
68581 22679
79708 25334
84499 68...

output:

-1
10
1
34
16
8
17
2
27
35
0
-1
23
10
27
17
25
-1
-1
8
2
-1
-1
4
-1
0
35
11
20
-1
5
14
-1
21
16
19
17
-1
11
14
8
7
-1
5
11
0
25
5
22
6
23
27
45
9
2
19
-1
27
-1
11
29
0
8
-1
2
27
12
10
1
59
16
8
18
9
5
30
-1
17
0
-1
20
4
6
-1
10
10
24
19
14
-1
27
2
12
-1
-1
23
-1
-1
10
6
0
10
4
23
26
45
-1
10
1
12
15...

result:

ok 100000 numbers

Test #79:

score: 0
Accepted
time: 176ms
memory: 96120kb

input:

100000 100000 100000
72149 22986
47354 51153
11537 89661
66068 23463
46589 65852
79326 56213
86761 55789
97993 41543
82964 46888
20153 79059
82045 67302
90659 25631
23965 6938
1441 15028
90443 11263
73040 61435
52918 12959
58346 28933
70910 58281
32006 72233
30126 49376
44807 81182
47385 21578
8395 ...

output:

20
11
9
-1
34
32
19
14
19
-1
0
-1
-1
24
43
14
46
29
25
-1
9
-1
18
8
5
-1
5
12
22
45
3
23
15
17
-1
54
34
-1
3
-1
27
22
-1
9
28
-1
23
11
11
14
6
17
-1
16
30
0
-1
22
0
16
27
-1
13
1
24
1
21
44
35
0
9
21
-1
40
11
7
-1
7
16
1
27
18
6
50
4
-1
-1
-1
12
-1
-1
9
-1
33
67
10
-1
28
18
17
11
10
25
10
-1
5
41
-1...

result:

ok 100000 numbers

Test #80:

score: 0
Accepted
time: 381ms
memory: 100236kb

input:

100000 100000 100000
3462 81204
70159 37925
99726 90429
70223 40799
14873 38559
37793 41930
3084 41312
68497 86159
47816 68688
52531 89953
1376 47438
47481 17192
50427 94865
35323 38504
13032 38727
76866 51566
6432 28529
56012 88866
87664 51725
66543 34832
38665 29700
13005 63825
11465 60844
97758 3...

output:

363
-1
20638
-1
1749
1274
35659
28702
-1
17403
-1
28550
7096
706
2293
5621
-1
20396
1894
-1
-1
-1
24794
8868
13100
15683
16594
-1
-1
31508
19218
-1
2193
4389
83309
9764
4348
-1
1736
42125
3554
773
13858
25984
172651
2107
29079
37640
126
23151
-1
91760
47322
617
25705
-1
354
23
3782
-1
38620
3555
255...

result:

ok 100000 numbers

Test #81:

score: 0
Accepted
time: 357ms
memory: 102104kb

input:

100000 100000 100000
6440 68083
66073 25401
3584 44669
79963 22146
48489 58934
81847 87
49561 50917
6327 38653
58373 74431
17538 20734
53647 51014
67704 34347
70869 54828
10747 16090
89989 85769
39289 61079
97523 76945
46135 82610
56274 59740
54106 10592
68134 35057
13768 33760
95414 94538
84764 297...

output:

-1
8240
-1
-1
-1
67865
-1
2188
33289
9340
17027
20236
47624
1861
13294
48875
10126
-1
24480
-1
9210
13188
132418
51317
28260
230
3964
48793
6336
254
-1
-1
47896
5304
56995
3052
51841
6627
-1
-1
3475
1792
-1
-1
29368
-1
58133
2534
33278
-1
2567
92079
-1
57730
2524
-1
44987
19922
30564
3679
-1
25513
1...

result:

ok 100000 numbers

Test #82:

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

input:

100000 100000 100000
91808 30135
50972 1146
84910 81985
16129 17033
94465 79583
32622 23280
85946 51452
65065 98903
89725 49004
99423 48534
77289 73564
37868 48152
9381 35924
93420 59986
23345 63366
3398 23404
93191 12953
77724 38411
90712 68002
5301 4862
20957 68048
98789 45225
61566 96473
32467 83...

output:

1437
1639
-1
1634
970
2143
-1
1030
-1
871
419
254
1283
1141
706
1223
58
-1
2185
149
-1
537
-1
2187
421
13
-1
884
794
2262
139
1297
762
-1
-1
0
1127
683
-1
439
674
1541
941
216
-1
306
606
584
3
91
1835
1394
590
646
605
262
707
-1
-1
646
1600
730
1615
582
-1
1203
-1
-1
469
709
-1
1244
1443
-1
-1
539
1...

result:

ok 100000 numbers

Test #83:

score: 0
Accepted
time: 272ms
memory: 96004kb

input:

100000 100000 100000
24698 35289
46289 26709
98479 83522
61361 91082
92826 73228
88386 69076
91664 87385
47710 45812
89296 48474
97350 70457
93416 6674
24426 91862
53161 6787
35468 84017
35834 12050
63115 27062
19917 69932
2076 33274
94156 60820
81164 50190
57642 63582
80986 70979
42949 48804
48180 ...

output:

1347
251
1963
439
424
1328
-1
102
-1
-1
-1
129
1271
-1
1052
-1
663
384
835
-1
-1
88
1436
584
1148
361
1377
23
973
2167
581
-1
-1
-1
-1
2022
1113
574
-1
-1
1069
464
-1
608
165
33
553
-1
-1
1319
13
964
1489
-1
-1
490
828
-1
2798
1652
582
308
292
319
144
378
1091
2294
570
85
285
264
1099
1755
389
120
8...

result:

ok 100000 numbers

Test #84:

score: 0
Accepted
time: 298ms
memory: 95132kb

input:

100000 100000 100000
31726 31897
47233 87403
85872 46529
25017 23623
68959 97637
42534 18287
34875 6991
22652 72741
44213 47787
92443 99210
4470 63925
65226 7373
55198 59126
64158 19992
50768 70318
86429 22021
71056 34103
38392 39756
80274 31874
22840 70495
17857 17261
14398 28706
32431 21357
73018 ...

output:

231
1554
-1
-1
1252
1440
238
692
898
263
150
2003
1143
-1
2783
184
-1
137
689
607
-1
-1
-1
892
550
540
1429
-1
1314
-1
753
-1
365
-1
964
795
399
-1
732
-1
529
-1
284
746
199
-1
317
353
841
1510
-1
154
1656
1559
1251
1670
1199
225
220
68
430
387
670
197
-1
732
-1
656
-1
791
682
968
-1
242
-1
-1
-1
-1...

result:

ok 100000 numbers

Test #85:

score: 0
Accepted
time: 284ms
memory: 95908kb

input:

100000 100000 100000
96949 18925
31849 61027
99787 4907
99904 23646
44578 42279
66998 95970
95148 49428
50333 78127
64581 17975
74751 76118
87608 55710
95441 37403
50026 22735
74328 542
3822 55521
70770 86856
54958 91900
78366 20170
31914 55429
55983 80997
76890 16099
71149 98680
21538 34102
49832 1...

output:

1614
980
165
314
-1
944
-1
713
64
996
-1
-1
646
20
1275
1004
636
1285
1295
862
1314
422
287
471
1095
-1
-1
-1
906
814
469
1056
542
1226
370
2088
1046
-1
360
951
864
658
51
3462
530
-1
270
710
2265
9
-1
606
1203
896
1392
1615
220
531
-1
17
833
-1
-1
706
1188
386
-1
-1
1003
947
1955
210
-1
68
277
397
...

result:

ok 100000 numbers

Test #86:

score: 0
Accepted
time: 189ms
memory: 94684kb

input:

100000 100000 100000
46623 85181
46623 77979
69608 46623
46623 31612
46623 27495
46623 21126
28072 46623
65209 46623
46623 93628
46623 41537
88012 46623
46623 6770
46623 70331
46623 65925
99515 46623
43485 46623
46623 1558
46623 43805
33162 46623
46623 96253
46623 35058
46623 25848
46623 32222
33907...

output:

1
-1
0
1
8
6
-1
1
0
0
1
1
4
0
2
-1
-1
-1
2
1
2
0
1
1
0
1
0
1
-1
2
-1
2
1
-1
0
-1
1
0
3
0
0
0
0
1
2
0
-1
-1
0
0
0
2
0
0
-1
-1
-1
1
5
7
2
0
0
2
0
0
1
0
-1
6
2
1
0
4
0
0
0
0
1
1
1
-1
0
1
0
-1
0
1
0
3
4
1
1
-1
0
5
-1
0
0
-1
0
-1
-1
1
0
-1
1
4
1
3
-1
0
3
1
3
-1
1
1
-1
-1
0
0
-1
1
0
-1
3
0
0
0
0
0
0
-1
1
...

result:

ok 100000 numbers

Test #87:

score: 0
Accepted
time: 175ms
memory: 96396kb

input:

100000 100000 100000
88375 4501
4501 70362
4501 35178
4501 92482
4501 57056
4501 29644
96438 4501
49924 4501
42039 4501
4501 85879
36982 4501
70154 4501
14817 4501
40514 4501
4501 49331
10498 4501
4501 11241
82660 4501
4501 56580
45356 4501
22015 4501
55932 4501
63505 4501
4501 88476
33885 4501
4501...

output:

-1
2
3
4
1
0
0
2
1
0
-1
4
0
2
0
-1
1
-1
2
-1
-1
1
1
-1
3
1
0
0
-1
-1
2
-1
1
-1
-1
3
3
-1
4
3
0
0
2
2
2
-1
2
1
1
1
0
-1
-1
1
1
2
0
0
-1
8
2
2
4
-1
3
4
1
1
3
1
0
-1
0
0
2
0
0
-1
1
8
0
2
-1
-1
-1
1
-1
1
-1
4
2
0
2
0
2
0
0
0
-1
3
2
0
0
0
4
7
3
3
2
-1
-1
-1
2
-1
0
0
0
0
-1
-1
-1
0
0
0
-1
0
2
2
0
1
3
0
0
...

result:

ok 100000 numbers

Test #88:

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

input:

100000 100000 100000
37474 40645
37474 20269
37474 48226
5787 37474
37474 78687
40383 37474
37474 17182
37474 36614
52109 37474
37474 69433
34556 37474
56855 37474
73682 37474
63431 37474
64849 37474
37474 4902
37474 609
20598 37474
37474 58445
69505 37474
37474 39726
37474 77352
37474 42150
37474 8...

output:

-1
-1
0
0
2
2
1
0
1
3
-1
-1
2
2
2
1
-1
1
0
-1
0
-1
1
3
1
-1
0
1
0
-1
0
2
-1
-1
1
0
0
2
1
0
-1
2
2
4
3
-1
3
0
0
1
-1
-1
-1
0
1
-1
0
4
1
-1
0
-1
0
-1
-1
0
-1
0
2
0
2
0
-1
-1
-1
0
1
1
3
-1
2
-1
4
2
-1
0
-1
-1
1
-1
0
0
6
2
-1
1
3
-1
4
7
2
1
0
0
0
0
1
2
0
0
1
0
4
1
-1
-1
1
0
0
2
2
-1
2
0
8
0
-1
-1
0
-1
0...

result:

ok 100000 numbers

Test #89:

score: 0
Accepted
time: 183ms
memory: 95260kb

input:

100000 100000 100000
19059 91267
40221 19059
19059 3846
57593 19059
19059 39471
67225 19059
19059 89524
19059 11737
45281 19059
37149 5458
19059 91469
71233 19059
95572 19059
19059 2941
52196 19059
19059 70621
19059 13804
19059 64847
19059 39940
19059 63619
19059 26748
55030 19059
19059 12674
36194 ...

output:

0
-1
-1
0
5
1
0
0
-1
5
4
4
-1
-1
0
0
0
0
1
4
2
-1
0
-1
0
0
4
0
-1
0
1
0
-1
-1
0
-1
2
4
0
0
0
0
-1
1
6
1
4
0
-1
4
1
-1
2
0
3
1
2
0
-1
1
3
-1
0
3
-1
2
1
0
3
0
2
2
1
2
4
-1
0
0
0
0
2
-1
1
0
8
0
2
0
0
0
2
2
4
-1
3
3
3
2
0
0
3
1
1
1
-1
0
-1
1
-1
-1
3
-1
0
0
-1
-1
1
0
1
-1
1
0
0
-1
0
2
-1
1
1
0
-1
0
0
0
-...

result:

ok 100000 numbers

Test #90:

score: 0
Accepted
time: 218ms
memory: 95284kb

input:

100000 100000 100000
32270 30442
64260 36773
19039 39817
59278 14016
50391 51901
14362 14141
93539 58593
87066 87046
78625 34446
94557 62983
88833 25398
19179 4092
27857 59477
14967 47384
36066 42916
11539 96472
45716 77843
72501 54173
54093 90237
58232 32818
98469 59909
41636 60007
85090 40774
4468...

output:

13
2
14
35086
29366
49438
73233
2
9
26481
66398
-1
58335
-1
93042
10
14
14
9
-1
-1
-1
2
14
61493
30003
-1
39994
10
-1
16
-1
48432
7
-1
21
13
33007
8
-1
31958
6
-1
1
6
0
1
-1
-1
69866
915
1
-1
-1
26877
1
-1
58317
-1
86852
2
1
15789
9
-1
-1
3932
-1
-1
-1
19781
-1
13
26
8028
24943
-1
62485
14
67097
6
-...

result:

ok 100000 numbers

Test #91:

score: 0
Accepted
time: 198ms
memory: 94400kb

input:

100000 100000 100000
50338 79962
86216 64906
65713 99214
76662 36285
54496 71214
67236 47153
4413 57465
64027 88932
62967 76666
68530 13231
83995 42654
47885 65378
34572 71786
8396 86109
13503 49040
77514 44893
41832 9570
86096 94451
45411 55845
47489 82337
10530 16575
26978 60677
37942 52640
36812 ...

output:

9
-1
5
41494
-1
4623
18012
-1
27433
62508
6682
-1
3
35880
-1
50955
92859
-1
46189
-1
18184
-1
53701
2
-1
3
34917
62705
-1
56355
20955
58435
5
2
8
-1
7
14
-1
0
83318
-1
74834
18216
30046
-1
6036
0
60884
1
-1
58417
907
2
27483
45552
-1
2
9
75204
-1
2
64437
16126
-1
-1
34286
-1
14
35660
-1
3028
4
4
-1
...

result:

ok 100000 numbers

Test #92:

score: 0
Accepted
time: 182ms
memory: 95492kb

input:

100000 100000 100000
24360 37452
85573 99168
46748 2778
18171 37251
98970 73545
87341 96427
22245 45865
69423 71482
96285 88774
3407 43196
70234 31139
27663 503
63675 99946
73037 3151
57132 96069
5102 43773
41089 25627
90594 37380
549 49876
32596 9221
50535 50840
22592 53607
34805 17397
20775 99884
...

output:

6
6
10
78241
-1
22130
7
5
0
40317
1
1
2
7287
21490
-1
-1
-1
-1
76595
22178
61916
-1
-1
5773
-1
-1
10
9
-1
-1
5
4
4111
20513
8
0
-1
60368
51606
12
1
-1
16024
33334
-1
44968
-1
6
49950
11
3
-1
424
6
-1
3148
0
-1
53518
7
2
-1
8
5
14
3
0
4
3
44287
8
18611
6
36090
4521
14
-1
5
25865
-1
3883
4
4631
-1
2
6...

result:

ok 100000 numbers

Test #93:

score: 0
Accepted
time: 131ms
memory: 94940kb

input:

100000 100000 100000
82137 71211
61922 23485
43468 10882
79720 31965
84041 47011
33541 94859
5160 60086
51684 67657
22492 30541
7658 70525
94395 32054
2368 54993
45518 44780
50376 50839
44680 28409
88542 28569
41156 81207
74717 56183
57854 66164
56444 10554
92353 68314
92043 65751
95850 53721
31749 ...

output:

22
24
8
20
0
50
0
-1
34
10
33
25
21
37
44
23
3
23
25
-1
-1
22
1
28
12
23
-1
33
4
29
25
12
0
35
39
3
45
0
20
-1
24
-1
7
41
26
40
-1
30
36
7
-1
-1
-1
26
30
22
12
2
27
24
3
40
30
21
13
23
33
-1
12
8
5
28
-1
-1
-1
-1
4
44
-1
19
29
-1
20
4
16
22
15
14
22
32
-1
32
17
13
26
13
13
41
-1
45
-1
-1
15
18
5
13
...

result:

ok 100000 numbers

Test #94:

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

input:

100000 100000 100000
98680 65596
41874 34915
50676 20281
91137 62834
23957 74587
37350 3090
79829 95104
64671 37795
5230 82316
96742 29449
78928 55134
98419 55583
5073 87395
33863 5999
61928 40410
79719 59631
83496 97087
96861 83154
92939 74574
67977 35697
21675 73001
87163 57211
38074 83079
96982 1...

output:

34
-1
11
11
18
25
6
-1
13
22
11
9
28
32
16
12
4
31
15
4
6
15
-1
0
-1
13
9
7
-1
-1
-1
31
23
17
-1
11
-1
22
-1
5
9
-1
-1
27
8
13
29
20
36
12
-1
14
19
-1
33
-1
28
13
15
0
24
2
-1
29
13
22
-1
1
5
-1
-1
3
23
35
16
17
-1
3
9
7
15
0
5
15
9
-1
-1
13
-1
7
29
20
-1
-1
18
5
-1
10
14
8
14
28
33
8
25
-1
0
37
19
...

result:

ok 100000 numbers

Test #95:

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

input:

100000 100000 100000
7455 66449
61250 77267
43520 4710
34534 24333
34687 61724
85828 77182
83176 63088
26659 10229
87876 60557
49456 7690
8134 83234
8440 30338
69763 10548
41927 45100
22482 83814
19308 93677
53744 92550
66590 11029
26013 31502
84274 87131
21870 2771
84083 59963
7914 35582
18756 1353...

output:

14
9
-1
0
11
6
1
-1
0
9
8
4
-1
7
5
8
5
17
5
6
7
8
14
12
0
2
3
9
0
-1
-1
4
8
-1
9
12
10
-1
12
5
16
-1
2
-1
17
2
12
-1
34
7
15
16
7
5
-1
4
3
-1
-1
-1
31
3
-1
12
-1
8
6
1
14
5
18
10
-1
15
34
10
10
2
2
4
10
0
25
10
15
4
8
18
3
-1
-1
4
3
7
0
8
4
28
3
4
10
-1
16
-1
-1
-1
10
5
9
18
0
-1
-1
13
2
21
7
11
16
...

result:

ok 100000 numbers

Test #96:

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

input:

100000 100000 100000
11724 51586
84744 20074
57029 40235
35412 98032
69343 60346
30378 98443
5034 55134
74043 87794
95444 5349
26079 53627
10222 12241
68246 58133
87419 21385
12001 31493
96348 64180
95433 80871
95063 65264
40230 43268
43384 23586
19896 65247
87578 86918
55467 22490
76642 72537
44004...

output:

0
0
10
9
18
7
4
18
3
17
-1
-1
-1
-1
-1
15
-1
11
7
-1
2
5
2
0
-1
5
4
8
24
-1
-1
13
-1
-1
14
14
-1
12
19
9
-1
-1
0
-1
19
9
11
-1
-1
3
-1
2
13
5
5
17
5
-1
5
0
4
16
-1
4
3
9
-1
-1
18
-1
-1
4
4
15
0
4
-1
18
9
9
-1
8
0
-1
0
1
19
18
13
-1
12
-1
5
-1
-1
-1
11
21
7
11
-1
-1
1
10
11
13
-1
6
0
-1
4
3
1
15
19
-...

result:

ok 100000 numbers

Extra Test:

score: 0
Extra Test Passed