QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#583005#9173. Touching Grassucup-team4435#AC ✓532ms23888kbC++206.5kb2024-09-22 17:57:362024-09-22 17:57:43

Judging History

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

  • [2024-09-22 17:57:43]
  • 评测
  • 测评结果:AC
  • 用时:532ms
  • 内存:23888kb
  • [2024-09-22 17:57:36]
  • 提交

answer

#pragma GCC optimize("Ofast")

#include "bits/stdc++.h"

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
#define rep1n(i, n) for (int i = 1; i <= (n); ++i)
#define repr(i, n) for (int i = (n) - 1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define each(x, a) for (auto &x : a)
#define ar array
#define vec vector
#define range(i, n) rep(i, n)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using str = string;
using pi = pair<int, int>;
using pl = pair<ll, ll>;

using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pair<int, int>>;
using vvi = vector<vi>;

int Bit(int mask, int b) { return (mask >> b) & 1; }

template<class T>
bool ckmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool ckmax(T &a, const T &b) {
    if (b > a) {
        a = b;
        return true;
    }
    return false;
}

// [l, r)
template<typename T, typename F>
T FindFirstTrue(T l, T r, const F &predicat) {
    --l;
    while (r - l > 1) {
        T mid = l + (r - l) / 2;
        if (predicat(mid)) {
            r = mid;
        } else {
            l = mid;
        }
    }
    return r;
}


template<typename T, typename F>
T FindLastFalse(T l, T r, const F &predicat) {
    return FindFirstTrue(l, r, predicat) - 1;
}


const ll INF = 2e18;
const int INFi = 1e9;
const int N = 8e5 + 5;
const int LG = 20;

struct Point {
    int x, y;

    Point(int x_ = 0, int y_ = 0) : x(x_), y(y_) {}

    Point operator-(const Point &oth) const {
        return {x - oth.x, y - oth.y};
    }


    ll operator*(const Point &oth) const {
        return 1ll * x * oth.y - 1ll * y * oth.x;
    }
};

using pt = Point;

pt a[N];
int n;
const int M = 3e5 + 10;
pt s[M], f[M];
int ord[N];

int ordR[M];
int ordL[M];
int ans[M];

int tmp[M];

bool check1(int i, int j) {
    if (ans[i] != -1) return true;
    if (s[i].x > a[j].x || f[i].x < a[j].x) return false;
    if ((f[i] - s[i]) * (a[j] - s[i]) >= 0) {
        ans[i] = j;
        return true;
    }
    return false;
}

vector<int> stk;
int sz;

void AddRight(int p) {
    while (sz >= 2 && (a[stk[sz - 1]] - a[stk[sz - 2]]) * (a[p] - a[stk[sz - 2]]) >= 0) {
        stk.pop_back();
        sz--;
    }
    stk.push_back(p);
    sz++;
}

void checkRight(int i) {
    if (!sz || check1(i, stk.front()) || check1(i, stk.back())) return;
    if (sz <= 2) return;
    int l = -1;
    int r = (int) stk.size() - 1;
    pt v = f[i] - s[i];
    while (r - l > 1) {
        int m = (l + r) / 2;
        if ((a[stk[m + 1]] - a[stk[m]]) * v >= 0) {
            r = m;
        } else {
            l = m;
        }
    }
    check1(i, stk[r]);
}


void AddLeft(int p) {
    while (sz >= 2 && (a[stk[sz - 1]] - a[stk[sz - 2]]) * (a[p] - a[stk[sz - 2]]) <= 0) {
        stk.pop_back();
        sz--;
    }
    stk.push_back(p);
    sz++;
}

void checkLeft(int i) {
    if (!sz || check1(i, stk.front()) || check1(i, stk.back())) return;
    if (sz <= 2) return;
    int l = -1;
    int r = (int) stk.size() - 1;
    pt v = f[i] - s[i];
    while (r - l > 1) {
        int m = (l + r) / 2;
        if ((a[stk[(int) stk.size() - 1 - (m + 1)]] - a[stk[(int) stk.size() - 1 - m]]) * v >= 0) {
            r = m;
        } else {
            l = m;
        }
    }
    check1(i, stk[(int) stk.size() - 1 - r]);
}

void solve(int l, int r, int lq, int rq) {
    if (l >= r || lq >= rq) return;
    if (l + 1 == r) {
        for (int i = lq; i < rq; ++i) {
            check1(ordL[i], l);
        }
        return;
    }

    int m = (l + r) / 2;
    ll xm = a[m].x;

    {
        int j = lq;
        sz = 0;
        stk.clear();
        for (int i = m; i < r; ++i) {
            while (j < rq && f[ordR[j]].x < a[i].x) {
                if (s[ordR[j]].x < xm) checkRight(ordR[j]);
                j++;
            }
            AddRight(i);
        }
        while (j < rq) {
            if (s[ordR[j]].x < xm) checkRight(ordR[j]);
            j++;
        }
    }
    {
        sz = 0;
        stk.clear();
        int j = rq - 1;
        for (int i = m - 1; i >= l; --i) {
            while (j >= lq && s[ordL[j]].x > a[i].x) {
                if (f[ordL[j]].x > xm) checkLeft(ordL[j]);
                j--;
            }
            AddLeft(i);
        }
        while (j >= lq) {
            if (f[ordL[j]].x > xm) checkLeft(ordL[j]);
            j--;
        }
    }

    int mL = lq;
    for (int i = lq; i < rq; ++i) {
        if (f[ordL[i]].x < xm) {
            tmp[mL++] = ordL[i];
        }
    }
    int eL = mL;
    for (int i = lq; i < rq; ++i) {
        if (s[ordL[i]].x > xm) {
            tmp[eL++] = ordL[i];
        }
    }
    for (int i = lq; i < rq; ++i) ordL[i] = tmp[i];

    int mR = lq;
    for (int i = lq; i < rq; ++i) {
        if (f[ordR[i]].x < xm) {
            tmp[mR++] = ordR[i];
        }
    }
    int eR = mR;
    for (int i = lq; i < rq; ++i) {
        if (s[ordR[i]].x > xm) {
            tmp[eR++] = ordR[i];
        }
    }
    for (int i = lq; i < rq; ++i) ordR[i] = tmp[i];
    assert(mL == mR && eL == eR);

    solve(l, m, lq, mL);
    solve(m, r, mL, eL);
}

void solve() {
    cin >> n;
    rep(i, n) cin >> a[i].x >> a[i].y;
    iota(ord, ord + n, 0);
    sort(ord, ord + n, [&](const int &i, const int &j) { return a[i].x < a[j].x; });
    sort(a, a + n, [&](const pt &i, const pt &j) { return i.x < j.x; });

    int m;
    cin >> m;
    rep(i, m) {
        cin >> s[i].x >> s[i].y >> f[i].x >> f[i].y;
        if (s[i].x > f[i].x) {
            swap(s[i], f[i]);
        }
    }
    iota(ordL, ordL + m, 0);
    sort(ordL, ordL + m, [&](const int &i, const int &j) { return s[i].x < s[j].x; });
    iota(ordR, ordR + m, 0);
    sort(ordR, ordR + m, [&](const int &i, const int &j) { return f[i].x < f[j].x; });
    rep(i, m) ans[i] = -1;

    solve(0, n, 0, m);
    rep(i, m) {
        if (ans[i] != -1) ans[i] = ord[ans[i]] + 1;
        cout << ans[i] << '\n';
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(12) << fixed;
    int t = 1;
//    cin >> t;
    rep(i, t) {
        solve();
    }
//    cout << sizeof(a) / 1'000'000 << '\n';
    return 0;
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 5ms
memory: 20564kb

input:

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

output:

3
3
-1

result:

ok 3 queries

Test #2:

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

input:

1
7 10
1
5 3 9 7

output:

1

result:

ok 1 queries

Test #3:

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

input:

2
33 7
86 14
2
72 74 56 83
70 95 100 66

output:

-1
-1

result:

ok 2 queries

Test #4:

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

input:

3
590 27
77 202
795 527
3
76 639 304 621
275 361 860 959
788 734 405 422

output:

-1
-1
-1

result:

ok 3 queries

Test #5:

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

input:

5
258 931
102 85
383 957
124 128
796 906
5
329 73 759 927
480 626 118 591
440 370 595 676
407 887 608 182
399 850 65 102

output:

3
1
-1
-1
1

result:

ok 5 queries

Test #6:

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

input:

8
515 549
180 48
6 444
280 37
860 488
17 622
457 161
915 348
8
424 777 116 971
323 964 277 458
4 482 804 312
770 206 244 512
971 178 688 265
531 426 320 591
736 230 865 762
552 762 454 129

output:

-1
-1
1
1
5
1
-1
7

result:

ok 8 queries

Test #7:

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

input:

13
335 343
437 210
961 689
756 260
716 897
899 129
424 638
179 109
742 319
135 378
561 658
205 18
598 724
13
911 515 141 839
78 158 981 973
571 643 962 720
112 604 755 516
80 339 410 773
192 638 458 45
347 818 629 857
44 606 76 950
269 990 644 872
556 97 298 783
44 619 752 978
119 74 28 214
902 226 ...

output:

5
11
5
11
-1
1
-1
-1
-1
7
-1
-1
11

result:

ok 13 queries

Test #8:

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

input:

10
92 583
165 167
58 286
62 426
156 591
673 825
640 518
254 791
102 651
197 154
10
798 988 642 805
637 34 533 820
926 453 952 99
289 626 798 261
489 612 719 420
441 522 975 262
845 782 988 920
229 807 454 810
270 720 967 281
945 187 250 604

output:

-1
-1
-1
7
7
7
-1
-1
7
8

result:

ok 10 queries

Test #9:

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

input:

10
580 141
638 496
866 385
438 257
759 113
479 705
963 957
812 555
616 986
548 992
10
612 256 901 196
809 867 277 212
995 108 957 8
292 194 922 835
934 864 838 966
972 483 649 763
568 762 19 827
712 894 961 920
514 519 734 947
276 698 492 827

output:

2
9
7
9
-1
7
10
-1
9
-1

result:

ok 10 queries

Test #10:

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

input:

10
411 160
78 181
160 292
586 903
76 152
337 349
603 339
245 326
734 532
812 18
10
735 47 816 111
799 113 664 236
490 291 28 392
419 672 795 228
473 66 583 800
520 12 157 224
59 18 617 507
690 383 744 83
22 306 545 123
819 137 22 23

output:

-1
9
6
9
-1
1
4
9
6
1

result:

ok 10 queries

Test #11:

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

input:

10
65 315
794 631
93 430
241 748
627 717
17 796
293 158
5 316
726 566
341 597
10
649 66 383 213
995 178 432 719
444 692 427 839
579 583 210 240
701 572 237 10
589 127 591 243
468 32 10 86
888 600 568 324
402 267 935 56
292 261 127 348

output:

5
5
-1
10
7
-1
7
5
5
4

result:

ok 10 queries

Test #12:

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

input:

10
1 731
733 836
217 848
666 864
864 698
740 427
464 695
369 694
356 707
316 594
10
40 485 971 195
124 99 694 29
747 235 841 73
831 105 619 128
840 220 770 154
690 649 9 21
163 400 280 398
247 610 475 325
824 258 62 684
259 673 911 370

output:

7
7
-1
2
-1
7
3
7
7
7

result:

ok 10 queries

Test #13:

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

input:

10
36 458
114 866
202 362
687 667
82 766
515 524
254 847
316 914
404 884
439 806
10
765 141 658 35
394 79 867 542
182 194 657 52
536 32 860 552
662 717 901 80
882 746 790 717
626 349 704 702
819 198 730 79
620 144 805 773
890 264 708 199

output:

4
10
8
4
4
-1
4
-1
4
-1

result:

ok 10 queries

Test #14:

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

input:

100
104375211 269633504
751249866 429319365
689374899 460732977
314375099 460732977
809374835 384816748
621874935 481675385
98750214 259162300
526249986 497382191
869374803 319371723
978124745 36649215
235625141 418848161
61250234 175392668
959374755 120418847
940624765 180628270
708124889 452879574...

output:

-1
-1
-1
80
95
-1
-1
85
-1
74
18
3
77
-1
31
-1
91
-1
-1
-1
-1
19
-1
93
-1
80
-1
-1
16
57
-1
-1
-1
92
24
58
93
93
80
80
-1
33
20
85
-1
39
57
92
3
80
-1
63
-1
-1
21
93
-1
93
-1
11
77
56
93
4
-1
39
6
11
-1
83
33
17
-1
-1
91
-1
80
32
8
57
25
53
-1
-1
-1
80
-1
93
-1
80
25
-1
21
16
32
-1
80
-1
-1
-1

result:

ok 100 queries

Test #15:

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

input:

100
578906149 184293121
327343971 93193681
311718991 53403121
527343715 196858561
687499760 60732961
628906085 153926641
382812650 162303601
310156493 48167521
674218527 93193681
559374924 190575841
693749752 39790561
442187574 190575841
613281105 166492081
455468807 193717201
378906405 159162241
40...

output:

-1
-1
-1
-1
-1
-1
-1
-1
79
32
27
53
10
80
-1
79
-1
100
47
-1
-1
-1
50
-1
100
52
45
35
32
53
100
45
97
4
-1
-1
-1
79
95
-1
49
45
71
93
53
-1
80
22
32
-1
-1
-1
-1
35
95
-1
-1
100
-1
-1
4
79
-1
-1
-1
-1
10
-1
35
-1
80
-1
-1
53
100
53
97
-1
-1
-1
-1
53
35
1
-1
55
-1
79
53
-1
-1
-1
-1
-1
100
79
71
-1
-1
80

result:

ok 100 queries

Test #16:

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

input:

100
689374899 184293121
290000112 180104641
610624941 193717201
361250074 190575841
38750246 39790561
265625125 174869041
21875255 5235601
44375243 48167521
194375163 153926641
168125177 143455441
809374835 153926641
942499764 70157041
98750214 103664881
882499796 119371681
209375155 159162241
90499...

output:

-1
-1
1
46
61
46
-1
-1
-1
70
9
3
-1
-1
-1
36
-1
57
76
63
-1
-1
-1
70
-1
25
79
-1
61
-1
70
70
-1
57
17
-1
57
4
70
-1
70
62
-1
-1
87
95
-1
25
99
22
25
25
-1
-1
70
-1
70
-1
25
-1
32
45
63
-1
-1
73
-1
70
90
40
97
-1
25
45
97
82
-1
70
69
-1
96
96
88
22
-1
35
4
-1
-1
-1
48
-1
-1
25
-1
34
6
-1
60
-1

result:

ok 100 queries

Test #17:

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

input:

100
464062523 494764390
206250188 335078529
832812287 269633504
860937269 198952877
193750196 316753922
154687721 232984290
245312663 384816748
673437389 452879574
554687465 492146589
410937557 484293186
898437245 36649215
826562291 282722509
867187265 180628270
176562707 282722509
101562755 1308900...

output:

70
75
-1
-1
-1
75
52
89
75
-1
-1
-1
-1
80
-1
85
72
-1
-1
71
-1
92
-1
24
86
-1
77
52
-1
52
75
62
62
5
80
72
-1
-1
-1
-1
-1
65
52
75
40
52
7
7
-1
68
-1
-1
52
70
64
77
-1
80
75
5
-1
-1
-1
-1
-1
52
-1
23
52
-1
-1
48
52
14
89
-1
-1
-1
-1
52
52
-1
-1
-1
-1
-1
27
53
-1
85
-1
-1
-1
100
-1
53
-1
-1
97
20

result:

ok 100 queries

Test #18:

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

input:

1000
99265 42424
6525 80276
43140 68127
51964 40908
9094 12209
56077 44140
35448 98852
28625 82098
19575 99100
71555 84605
82554 53440
66211 96383
32553 56834
24935 45751
93854 42815
48816 77595
43061 84311
28790 91865
82689 42188
14193 68109
25414 35706
42978 37435
95707 24033
5230 8768
98110 60382...

output:

819
543
816
852
588
852
670
289
852
844
410
852
612
852
588
894
852
852
671
103
356
622
852
852
245
588
588
588
714
852
852
347
874
852
996
95
447
973
819
852
852
588
662
735
702
852
852
350
852
60
60
852
588
852
852
852
39
702
430
852
852
794
1000
852
400
588
286
486
588
333
588
32
803
218
507
973
...

result:

ok 1000 queries

Test #19:

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

input:

1000
28300 86536
22994 53484
20020 15737
26356 89356
26753 11847
30605 50013
42932 18585
8899 72465
4411 49361
26585 90626
51327 84833
52365 90943
401 48310
10162 38550
50430 95099
1622 24788
12739 10766
14862 73531
33902 46319
32354 4223
11820 34406
45407 20670
14396 75226
75914 58613
8972 69295
27...

output:

941
186
187
981
626
859
705
124
225
109
642
895
859
124
981
981
865
870
212
628
382
981
212
895
847
98
705
409
826
409
642
894
186
382
893
212
109
544
945
382
80
573
382
385
832
853
98
859
504
731
124
409
24
415
212
186
572
893
212
544
981
94
935
731
981
385
731
731
212
981
186
945
212
870
124
859
3...

result:

ok 1000 queries

Test #20:

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

input:

1000
78977 2074
66043 47947
64156 52000
51800 85017
72769 95309
46109 79414
36736 33830
49795 80993
55338 34213
43064 76999
65173 82889
66315 3970
99433 51579
66787 4438
58356 6041
93272 76919
50078 59284
56182 1396
67908 10035
43286 8887
97186 26326
96899 31500
63434 29455
48732 30636
35450 11558
9...

output:

981
303
303
522
287
303
942
303
303
353
458
353
972
303
303
942
173
458
931
287
445
248
430
303
303
857
755
276
303
303
303
417
762
303
491
248
303
102
303
303
71
931
931
303
303
353
353
303
287
303
303
71
303
303
303
303
931
931
303
303
353
720
303
217
303
495
71
762
217
303
749
931
248
799
287
248...

result:

ok 1000 queries

Test #21:

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

input:

1000
36848 40244
44170 64859
73782 6532
73472 36699
46777 34630
63459 23868
78986 72094
26865 4675
77925 17395
47410 23785
94705 11395
33118 67032
22374 19144
80516 8954
18542 45485
98758 26287
74867 20978
12033 1526
46253 7927
98382 56613
5121 17203
79008 36907
43003 28552
26916 58370
19889 4914
67...

output:

906
963
60
906
474
270
476
282
636
145
617
270
843
4
419
489
270
906
541
980
906
627
541
963
906
222
589
222
324
320
541
858
270
602
721
916
541
906
627
894
413
799
270
532
906
147
144
750
270
963
16
270
945
906
222
381
280
986
602
639
636
307
270
918
906
636
270
640
525
381
577
242
541
589
320
413
...

result:

ok 1000 queries

Test #22:

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

input:

1000
68145 63988
20049 98052
65320 22484
51398 26637
97914 51952
59106 47893
72627 33233
29799 7761
46724 11815
12844 6192
33841 34192
77477 42156
34099 67744
35764 32534
48996 75348
2282 58347
88521 63517
52160 16252
4725 36435
49709 34142
24477 86718
15505 15637
92399 27917
93836 96166
15947 48818...

output:

-1
86
575
368
523
603
956
410
-1
905
86
468
523
24
-1
532
575
532
617
617
309
308
308
255
411
181
279
532
523
368
368
86
433
854
523
229
523
523
309
575
410
840
391
785
310
256
532
523
551
627
523
532
956
197
153
687
976
776
617
153
860
309
523
368
86
198
86
86
956
-1
617
86
985
523
523
840
343
485
...

result:

ok 1000 queries

Test #23:

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

input:

1000
32262 64303
61279 44889
65478 96756
56972 89836
44573 79202
44593 95816
14861 37219
39343 89033
9952 60289
45649 51122
97456 86044
9778 80279
67982 59088
9670 68241
96441 28060
21016 68624
39423 73225
42680 27947
13255 72628
99637 80438
47774 87915
22076 84626
92140 53091
87815 38151
13374 9221...

output:

936
936
577
615
936
528
936
606
382
936
936
309
936
709
309
175
936
936
936
936
709
936
936
577
376
309
936
709
936
936
936
936
936
936
936
936
709
577
76
177
936
936
936
936
757
606
709
76
709
606
936
709
936
709
936
709
936
936
175
376
936
936
936
936
936
936
606
709
936
936
606
104
936
606
709
43...

result:

ok 1000 queries

Test #24:

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

input:

1000
34857 67019
7415 19038
58888 94480
24948 36803
4940 97142
6746 73658
12646 64268
8936 83873
26881 43000
13264 45746
29912 79916
63241 96138
23329 38401
13070 78956
71587 84047
54276 87450
4314 66647
45825 75136
11422 96929
17321 83961
64272 56369
5721 67445
6924 54753
11517 42364
30176 46402
75...

output:

507
507
768
507
504
930
507
507
390
768
69
245
768
524
69
768
504
880
768
208
69
768
390
390
350
245
-1
507
507
507
390
665
768
69
260
507
632
768
390
390
126
676
507
507
507
390
357
507
768
390
507
665
390
228
390
69
534
507
390
390
676
853
507
357
728
390
768
768
768
184
507
824
238
800
245
390
35...

result:

ok 1000 queries

Test #25:

score: 0
Accepted
time: 8ms
memory: 20780kb

input:

10000
38272240 171963896
85763537 299021340
209046366 429572370
100566222 323438826
348521793 484670406
683539908 476578264
58128140 238845144
29955072 128921788
390127712 492238275
568014266 497017858
70914001 269704370
596910178 493996823
814144879 413794809
20346155 19534460
68799013 265021178
85...

output:

8602
4201
1274
7787
-1
3807
6942
-1
8012
-1
1953
-1
3471
126
-1
4688
8324
6881
2244
1448
-1
6981
-1
-1
-1
225
-1
-1
-1
9652
-1
3859
-1
3407
-1
6768
706
-1
5023
-1
3857
1993
8681
3627
-1
-1
-1
-1
-1
-1
3972
711
5245
3487
-1
7288
8607
8317
-1
7485
4741
-1
1274
4529
-1
511
-1
9958
-1
4729
9865
-1
6548
...

result:

ok 10000 queries

Test #26:

score: 0
Accepted
time: 9ms
memory: 20728kb

input:

10000
538046266 197784461
476080108 199045941
663791061 132905661
631533394 164931461
340414522 138392441
499419375 199834601
366910531 163795941
674331495 116306201
461428849 197724301
694164716 60114881
400704764 182737881
560764961 194261341
365066466 162412261
620699396 172029401
664760937 13156...

output:

5599
8776
140
-1
-1
7431
3980
-1
3591
1048
184
-1
895
-1
-1
692
-1
-1
-1
6318
-1
7520
3212
-1
-1
8961
-1
-1
4968
130
-1
-1
-1
8664
9472
-1
-1
8184
4917
-1
-1
-1
-1
-1
9512
8119
7078
314
-1
-1
2656
794
7243
9507
-1
3453
7320
1122
5608
-1
8992
-1
-1
-1
4550
6573
-1
-1
1901
-1
-1
3096
9560
-1
2578
9992...

result:

ok 10000 queries

Test #27:

score: 0
Accepted
time: 10ms
memory: 21976kb

input:

10000
966569030 59529261
112676090 136241721
793202482 171189981
571992139 198585341
732637525 183723941
20747735 12892101
683252109 190583121
907025871 124519921
48407673 83990881
254143800 181424701
155339503 155319021
751353384 180404801
120315034 140204761
918000160 116802521
99742983 128818541
...

output:

3871
2274
6019
-1
5758
-1
-1
9574
9439
-1
9040
2566
-1
4137
8283
-1
674
2951
3936
-1
6822
1027
-1
-1
3005
559
2700
1066
-1
-1
-1
-1
4305
-1
-1
-1
1967
9518
-1
-1
6040
4558
6531
3684
9512
537
-1
-1
7834
-1
-1
-1
6166
7209
5730
1227
4946
3857
-1
-1
-1
5156
8811
-1
5758
5547
-1
-1
-1
-1
4462
7317
27
-1...

result:

ok 10000 queries

Test #28:

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

input:

10000
102060601 62886900
627280153 484390637
100184870 11682120
102434260 68830228
463939118 498680015
867963024 239597464
456246576 498153391
893113435 117470067
152868930 294737818
899722180 17406805
112567669 157035046
891276743 131860538
344381251 475642566
775896049 400445831
794264828 38029070...

output:

6145
-1
-1
3581
2094
3936
-1
2441
40
1407
-1
-1
5989
-1
-1
-1
-1
-1
2719
-1
-1
-1
5585
2805
4658
-1
-1
3776
2624
-1
4875
5639
5753
-1
4029
-1
-1
5823
6439
6394
-1
-1
9431
2952
-1
5588
3352
8297
-1
-1
3722
-1
927
-1
6570
-1
7946
4301
8059
8546
8729
416
8546
-1
-1
5485
-1
-1
-1
5562
6531
4057
5984
-1
...

result:

ok 10000 queries

Test #29:

score: 0
Accepted
time: 174ms
memory: 19608kb

input:

1000
950113785 186384430
159684420 380691928
423030085 495461044
956718680 161922916
650997055 482691826
96120480 297230473
28763630 87692221
222855990 430845724
250779655 446691862
416817560 494768737
980064695 1153846
34256810 120153727
789634455 422768809
456250745 498230272
231488130 436153411
2...

output:

813
-1
123
745
866
-1
-1
268
901
512
-1
-1
918
86
-1
71
-1
123
798
-1
-1
410
87
585
-1
606
700
-1
-1
352
-1
444
-1
902
-1
-1
-1
880
-1
-1
736
-1
-1
946
-1
448
-1
-1
-1
91
828
16
663
443
295
268
576
995
438
-1
236
-1
802
143
468
802
-1
-1
587
-1
-1
-1
273
552
365
780
457
400
754
-1
874
844
-1
-1
-1
-...

result:

ok 300000 queries

Test #30:

score: 0
Accepted
time: 169ms
memory: 22400kb

input:

1000
697377268 28215174
392183621 176644830
692908760 53845751
570106531 191260105
355781629 149906569
345427769 138460501
699230064 11261455
529617489 198429282
557845381 194213929
388913981 174890997
651248097 142522009
310115657 66122582
475750170 198890817
388178312 174491000
673645131 109291489...

output:

541
897
825
-1
853
841
929
564
-1
107
827
-1
-1
170
298
335
411
-1
-1
-1
703
141
-1
-1
-1
-1
107
-1
687
845
-1
201
726
-1
853
386
20
314
851
-1
-1
-1
-1
955
-1
653
572
494
-1
13
933
532
654
841
482
-1
-1
-1
170
814
277
934
-1
-1
386
121
236
897
-1
726
147
94
386
-1
-1
-1
892
386
-1
107
959
-1
-1
-1
...

result:

ok 300000 queries

Test #31:

score: 0
Accepted
time: 169ms
memory: 22348kb

input:

1000
271640660 182644785
671792665 190860108
39096040 57476493
66104175 93568530
77025140 103937683
73755390 101014628
597046180 197198522
756217610 177229441
28044285 33107445
63030610 90337785
68916160 96399278
20981625 6092263
728490130 182644785
922647885 104337680
58060590 84737827
23074265 162...

output:

670
-1
211
338
-1
160
86
846
183
35
706
750
206
730
500
541
-1
-1
846
-1
630
147
-1
669
-1
-1
-1
-1
649
472
483
665
-1
-1
-1
319
326
-1
-1
1
-1
21
-1
670
284
-1
952
643
-1
915
-1
553
527
361
-1
-1
959
-1
730
-1
326
-1
826
-1
-1
-1
-1
-1
117
984
650
-1
7
378
307
-1
984
569
-1
-1
310
-1
-1
-1
348
-1
-...

result:

ok 300000 queries

Test #32:

score: 0
Accepted
time: 233ms
memory: 23164kb

input:

800000
784741874 210533410
353085426 422755675
781708646 222556219
506812566 458364034
622169826 435235123
805863650 34374448
645900698 423339673
605188280 441890482
729903354 343317577
516837948 458064559
207100590 171244993
805215474 52868296
323627088 402563830
193698202 8877208
731245436 3412825...

output:

212624
-1
347536
263915
522222
456498
628124
-1
-1
248430
-1
366142
69668
509092
-1
223061
318985
-1
-1
110945
9258
-1
-1
462461
-1
359491
58835
-1
313798
509172
124584
138493
386447
88431
348978
672438
226148
-1
-1
282
-1
515671
127478
447594
355875
200549
-1
407365
-1
206383
12109
130807
-1
62393
...

result:

ok 1000 queries

Test #33:

score: 0
Accepted
time: 482ms
memory: 21848kb

input:

800000
15080485 373982169
614292757 749424468
378357740 628541521
79381350 843893217
453124596 119687443
484302417 974146980
516574553 714424410
430785761 282534933
619155709 566316775
649254128 947571187
579369273 470081889
732948204 583913287
625089279 367784769
945725299 140561959
209803202 62339...

output:

799212
251135
194692
194692
735206
684408
530990
461885
569909
194692
642220
608568
103308
22302
194692
627495
701827
194692
569909
194692
569909
194692
194692
569909
329317
5627
194692
569909
194692
569909
137551
619865
16563
357264
357264
36113
247498
569909
194692
194692
104803
194692
194692
4566...

result:

ok 300000 queries

Test #34:

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

input:

800000
970862261 177937361
320989261 359990571
312920234 84857429
506272064 53645521
670985814 111918467
981396383 144694379
874534410 89958190
632186002 67853132
401513257 615236965
950421177 140354653
163951033 125742729
346216429 321373855
348435258 69323315
197782340 66308601
320792790 185377967...

output:

190739
301532
544332
764312
556614
232121
657421
284881
213265
95713
504092
152965
301532
213265
87007
783966
203964
584661
282020
98244
584661
152965
301532
657421
355865
188543
152965
195352
502140
213265
779475
213265
213265
793007
213265
172583
152965
491360
724309
262629
152965
178442
70048
137...

result:

ok 300000 queries

Test #35:

score: 0
Accepted
time: 486ms
memory: 22056kb

input:

800000
356316339 447808912
751110608 792107918
99787335 360590392
635903936 892982116
589354691 432044768
736118372 905462318
115688455 353611127
468465955 811503516
684297455 707955369
406557555 800894802
377108926 805379888
485562074 944224487
852274684 653824477
205450280 368507930
406144647 7949...

output:

187076
729594
625903
187076
187076
696574
489129
696574
187076
783164
696574
187076
144204
187076
86541
664762
696574
489129
696574
22579
444134
187076
187076
696574
187076
502713
672640
756565
177403
22579
672640
490206
200688
187076
187076
625903
672521
187076
696574
187076
187076
625903
187076
62...

result:

ok 300000 queries

Test #36:

score: 0
Accepted
time: 467ms
memory: 22164kb

input:

800000
435968634 684362547
441064604 505046464
620484857 319028341
792345009 848373099
406573813 192217214
787140656 668338086
230367139 87502268
7703404 901849512
455820381 774559804
562289268 135429218
520747368 875359996
432291380 821751357
648738114 190011349
727553490 530479798
407700356 797048...

output:

317455
467401
163469
163469
163469
163469
317455
768331
117779
538040
163469
163469
163469
509152
98222
321822
618067
78773
90746
692624
287950
229728
261014
192751
330557
163469
163469
474531
163469
280141
163469
639058
409628
474531
791280
789287
163469
163469
163469
528965
163469
347164
653494
33...

result:

ok 300000 queries

Test #37:

score: 0
Accepted
time: 468ms
memory: 22444kb

input:

800000
143880629 433393385
193643808 401935625
734144605 58191320
190108233 190306639
307572084 749789023
121817450 260320727
134903541 534247251
409365097 625924172
424385045 60106896
252114717 122961448
42626244 383252808
751403226 173229739
46834403 459189568
359323778 215474092
882772085 3671827...

output:

300344
619091
619091
92223
159352
340693
300344
169234
300344
697325
286298
125203
446209
763418
303454
619091
272310
739298
693273
697325
399440
565976
500494
303454
241396
556118
619091
125203
537120
651709
340693
697325
446209
329972
761190
697325
329972
697325
241396
748324
614503
377021
241396
...

result:

ok 300000 queries

Test #38:

score: 0
Accepted
time: 459ms
memory: 22372kb

input:

800000
120950448 879584359
488651784 384240390
50352543 580051609
684557638 854032618
100203234 982242049
217991920 559662067
213687995 844385542
640792989 809993298
293538395 394639002
55549277 500280434
233493640 173065576
282807645 701191513
358926465 109895126
302448777 536794411
48385886 772998...

output:

485488
485488
15952
539277
15952
702560
485488
485488
749460
15952
324661
736342
761193
539277
485488
15952
171800
749460
485488
539277
539277
734979
15952
485488
372633
236853
228103
485488
15952
558778
136456
15952
485488
311747
460638
749460
539277
749460
15952
485488
15952
539277
539277
539277
1...

result:

ok 300000 queries

Test #39:

score: 0
Accepted
time: 485ms
memory: 21968kb

input:

800000
258986337 48032349
495126669 937655014
363138946 448769089
947944161 53929755
695238886 486364930
892505590 867548021
875030640 945391816
977957428 818317778
651160767 12263458
769679148 273876574
587102465 436376813
886111321 650487953
923548509 996735880
941414107 662118453
515705115 756515...

output:

642802
642802
642802
734697
642802
642802
642802
32363
427974
32363
32363
688015
642802
642802
499028
8018
734697
642802
536967
642802
642802
642802
486879
642802
415434
403482
642802
382751
734697
734697
64325
594015
642802
642802
642802
642802
642802
760805
642802
580867
642802
486879
642802
77310...

result:

ok 300000 queries

Test #40:

score: 0
Accepted
time: 491ms
memory: 22424kb

input:

800000
641334233 187074003
875766628 667554002
336586126 18610447
676448239 499188275
621023240 769515237
625565226 349609934
308558729 152015742
452394191 284105986
984185478 657079647
11781168 368322295
713554606 117993246
985186221 94429578
923572297 942840885
977883542 451479220
601049999 244349...

output:

653012
559528
353954
59367
408054
790198
353954
353954
397614
408054
112190
353954
556831
353954
397614
397614
790198
539104
353954
82796
353954
59367
353954
58031
722086
612534
620042
639242
397614
568783
704811
475804
59367
743079
353954
142968
543325
59367
408054
353954
145114
82796
353954
397614...

result:

ok 300000 queries

Test #41:

score: 0
Accepted
time: 487ms
memory: 21896kb

input:

800000
682431823 998431836
406575665 715536389
841120406 907463684
793426356 829068871
934050284 751400755
623576408 532345158
336831574 979273896
267559821 851441101
580059710 848375997
857971070 917959840
997245552 635406298
989754491 416304670
767863602 676672360
967769179 400935506
401530137 450...

output:

706721
526383
619730
706721
619730
706721
526383
47119
706721
337502
706721
706721
706721
526383
706721
706721
706721
706721
677463
706721
706721
706721
706721
706721
706721
526383
156414
93461
99007
119561
706721
706721
526383
619730
706721
706721
526383
706721
706721
706721
706721
619730
619730
70...

result:

ok 300000 queries

Test #42:

score: 0
Accepted
time: 474ms
memory: 22224kb

input:

800000
260900518 163178668
316985323 38366297
864012643 36553540
639356817 372141031
901980026 653040850
979372608 57617402
463572691 67613183
465802714 237038526
984756848 217872622
400002897 37109692
508000917 448629376
807796704 247261183
374507931 33039202
376743300 20719885
182372501 150756837
...

output:

242462
131506
688857
564239
40462
564239
696051
766551
554557
564239
564239
438802
456140
564239
479724
564239
282011
564239
564239
242462
194354
438802
696051
498867
479724
40462
498867
564239
80336
696051
242462
564239
354325
706075
601368
479724
34017
564239
-1
564239
498867
564239
564239
564239
...

result:

ok 300000 queries

Test #43:

score: 0
Accepted
time: 459ms
memory: 22460kb

input:

800000
251619778 603625954
88806435 329362117
123326212 392067283
296890364 355020689
453945473 85562108
371565146 158989343
6919200 580245649
73059719 45172878
328198756 4456177
616630236 812681826
508575995 177693374
50473678 49420471
33162113 377776961
389279708 556666414
400663114 454419600
2785...

output:

45102
455063
17598
317659
699677
231755
228836
45102
111466
199105
334549
505631
45102
135959
228836
455063
111466
199105
538505
566270
45102
391100
121693
45102
538505
45102
228836
180966
180966
795822
45102
40346
519431
714751
507386
40346
45102
203398
497700
460008
228836
566270
45102
402140
4034...

result:

ok 300000 queries

Test #44:

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

input:

800000
431411522 229477104
848697968 348780310
898224829 132660945
507266195 347040936
993745897 80751505
321545732 33082073
878225728 84657346
209237198 82627583
841969289 207966358
624596318 250828990
996107002 180430843
358130378 12508253
441659996 123282966
194576559 234455130
980404912 38272182...

output:

575326
564897
564897
575326
575326
575326
707064
796918
575326
16760
12246
169228
368483
-1
77778
599716
312614
169228
16760
673170
575326
575326
277505
672240
557880
575326
564897
575326
169228
379112
575326
379112
368483
582467
575326
39184
-1
508226
312614
508226
277505
564897
-1
407410
379112
57...

result:

ok 300000 queries

Test #45:

score: 0
Accepted
time: 431ms
memory: 22424kb

input:

800000
188938795 288699575
67887586 105641896
32659451 156569107
296727786 203608279
484158735 163446877
566391153 534307510
307733866 600060663
20710145 929949
432850012 187395623
139988134 18857803
40336164 528819843
33665824 69337269
458879498 322488348
293366055 70654341
374090214 494658918
2922...

output:

638686
108944
638686
-1
638686
638686
243098
-1
638686
-1
105828
638686
105828
234712
782266
-1
-1
638686
-1
148211
234712
342543
85193
234712
638686
638686
-1
638686
-1
-1
-1
-1
638686
105828
631545
638686
638686
509079
631545
509079
-1
-1
638686
638686
638686
638686
-1
-1
638686
509079
-1
234712
6...

result:

ok 300000 queries

Test #46:

score: 0
Accepted
time: 503ms
memory: 21888kb

input:

800000
360084296 195820110
910757589 108972900
308092165 6844895
671280725 135888029
391985030 78719755
793012367 138559273
832866938 99804758
784742353 332383861
644722058 59402949
412571121 24988121
678975223 547753759
255669626 46173402
668079205 198930675
336540127 145350434
607058233 34893572
3...

output:

328857
-1
149819
-1
-1
328857
149819
76101
-1
-1
-1
-1
-1
666677
328857
149819
569836
-1
-1
149819
708066
246178
798088
74448
-1
654070
294608
273416
-1
564093
-1
798088
-1
149819
798088
-1
-1
149819
-1
654070
-1
-1
745449
666677
-1
-1
798088
487814
708066
229306
54464
46479
525801
-1
328857
525801
...

result:

ok 300000 queries

Test #47:

score: 0
Accepted
time: 451ms
memory: 22332kb

input:

800000
152842815 74697484
203259578 28007914
411824102 137543311
438454387 197483150
336272234 310863327
17202834 532334222
619796690 62775834
394092189 99135257
349748840 122319719
167450725 108884484
658117474 69039084
98604967 161108018
287641562 13743817
447122406 190157107
325304405 218288364
6...

output:

-1
-1
-1
305551
305551
-1
554340
-1
-1
-1
-1
-1
391890
-1
-1
-1
218926
-1
-1
-1
-1
218926
-1
391890
-1
554340
706641
-1
391890
-1
-1
-1
-1
218926
-1
-1
760939
305149
-1
-1
305551
-1
698033
-1
-1
737130
305149
-1
721687
-1
698033
-1
-1
-1
-1
-1
391890
-1
-1
-1
-1
-1
228382
-1
-1
391890
-1
-1
-1
61732...

result:

ok 300000 queries

Test #48:

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

input:

800000
452584216 922884157
457016389 40191615
541267135 947490269
900953178 784029360
473550884 368219633
128951937 356906008
193915529 753085777
73540235 582645630
25564006 145574750
221031041 782127628
202616412 683241591
515050143 344401923
92110669 153190440
767616743 12663196
817130062 97449849...

output:

51181

result:

ok 1 queries

Test #49:

score: 0
Accepted
time: 125ms
memory: 21924kb

input:

1
693086739 667763491
300000
852876012 399679873 98139376 514550845
629716446 118469668 422688498 675874478
191667130 784447016 910409525 191474380
733775741 334768736 577278115 159083409
942644283 632600216 227316798 70214581
217095745 317102913 744033805 549805139
573318369 63393487 979854392 9169...

output:

1
-1
1
1
1
1
1
-1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
1
1
1
-1
-1
-1
1
1
-1
-1
1
-1
1
-1
-1
1
-1
1
-1
1
-1
-1
1
-1
1
1
-1
-1
-1
-1
-1
-1
-1
1
-1
1
1
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
1
1
-1
-1
-1
-1
1
-1
1
1
-1
1
-1
-1
1
1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
1
-1
-1
1
1
-1
1
1
-1
-1
1
1
1
-1
-1
-1
-1
-1
1
...

result:

ok 300000 queries

Test #50:

score: 0
Accepted
time: 405ms
memory: 22544kb

input:

800000
41248511 34357201
574577849 454048096
517186397 457183807
950307677 118677109
884752946 293758867
523251953 457045759
40963937 26801584
830652521 355644061
44452118 79190785
210502025 386830117
660988142 440055658
856475984 329978251
886582946 291023758
40526786 5722294
45751877 90901372
1542...

output:

244362
159383
261344
161074
159383
636105
261344
636105
512536
161074
159383
512536
261344
244362
492833
176722
636105
708685
636105
159383
538196
159383
159383
512536
161074
636105
727200
455884
159383
636105
400696
512536
538196
512536
636105
161074
496594
636105
700905
159383
496594
244362
299526...

result:

ok 300000 queries

Test #51:

score: 0
Accepted
time: 382ms
memory: 21856kb

input:

800000
632173228 91701637
346877067 4551964
458234225 149131846
357215851 68661617
652055837 24284057
352179990 51178978
636843939 82964895
347145301 12845078
354979892 61790667
361791238 80058138
593478354 130824625
368260289 92433013
359998066 75930841
600766613 126057656
644994608 61875640
597806...

output:

737966
737966
737966
737966
441150
737966
737966
737966
441150
737966
737966
441150
737966
737966
737966
737966
737966
737966
441150
737966
737966
441150
737966
737966
737966
737966
569863
441150
737966
441150
737966
737966
737966
737966
441150
737966
441150
441150
488508
737966
737966
737966
737966...

result:

ok 300000 queries

Test #52:

score: 0
Accepted
time: 399ms
memory: 21788kb

input:

800000
65757188 62689869
269370626 139188157
955510583 26518114
885050060 97772881
496458959 152446911
52161959 44208254
803719241 125720052
165125090 117275485
383955854 149639430
679628288 145065526
446211764 151891384
55291808 49323469
669690275 145960450
951580034 36874392
922974215 73479708
124...

output:

347967
102721
324826
744901
324826
323979
260354
504733
504733
217155
347967
324826
347967
519397
347967
217155
323979
323979
323979
347967
8666
658730
324826
324826
347967
323979
323979
417783
408473
324826
260354
744901
360756
72287
323979
504733
504733
347967
323979
324826
408473
347967
347967
32...

result:

ok 300000 queries

Test #53:

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

input:

800000
626237280 432349696
757003288 292641805
789494698 188072122
530105498 456180097
745028798 317009065
358140544 424528240
737435850 330335983
765006744 273409711
749242508 308949679
803641694 80019814
802061922 100008973
586576564 446588914
806114548 22337197
741009196 324243457
242852116 29231...

output:

274977
87251
334667
274977
87251
274977
122264
113961
122264
87251
116824
87251
688937
334667
87251
688937
334667
334667
298109
334667
87251
113961
688937
473478
298109
273363
274977
298109
87251
298109
3839
688937
87251
116824
274977
334667
274977
87251
87251
298109
688937
473478
570150
298109
6889...

result:

ok 300000 queries

Test #54:

score: 0
Accepted
time: 403ms
memory: 21768kb

input:

800000
834077927 353574577
845292725 342821431
179770262 365538184
41078210 31078891
501405284 458363770
154508981 342621811
99047747 268364593
98591429 267540160
153833189 341938897
71886272 207678379
349756385 443540857
957461744 58130191
518351111 458177836
911861876 247140037
427626734 455265973...

output:

757331
757331
257313
745574
720073
720073
745574
757331
757331
757331
757331
223278
269298
257313
257313
757331
703467
757331
269298
757331
755992
257313
269298
257313
257313
269298
269298
257313
269298
269298
757331
623577
269298
755992
757331
269298
757331
757331
745574
269298
118924
118924
269298...

result:

ok 300000 queries

Test #55:

score: 0
Accepted
time: 374ms
memory: 21492kb

input:

800000
407480143 131734528
652650345 16928867
612352630 116938859
359609733 75323895
646223710 57906840
511991534 152543911
644199740 64780746
570662214 141945763
386352125 115704752
349585185 37944390
507601730 152691542
573150238 141017833
416490931 136548124
597131713 128872230
347033667 10562730...

output:

485727
485727
485727
485727
485727
485727
626271
626271
485727
485727
794779
251373
794779
794779
485727
485727
251373
251373
485727
794779
485727
251373
485727
251373
485727
485727
485727
251373
485727
485727
485727
794779
251373
485727
485727
251373
485727
485727
251373
485727
485727
251373
485727...

result:

ok 300000 queries

Test #56:

score: 0
Accepted
time: 411ms
memory: 22484kb

input:

800000
452109830 152349175
421461659 151562477
679460231 145420349
905086145 86902172
911099447 82911948
659512748 147141905
811841360 124054540
50505656 41502399
941064599 54843818
45837596 30876979
56107313 50885233
82921988 78562940
51926471 44130724
714515573 141637218
654484334 147531551
735109...

output:

166787
28424
28424
56629
166787
412527
412527
166787
166787
751875
727049
412527
497115
635094
686658
70503
727049
727049
412527
727049
28424
28424
727049
166787
56629
35106
166787
727049
166787
412527
28424
686658
727049
143941
28424
519976
727049
166787
635094
28424
412527
727049
56629
28424
28424...

result:

ok 300000 queries

Test #57:

score: 0
Accepted
time: 396ms
memory: 22596kb

input:

800000
674001270 404386768
228695254 257093488
389105760 439754404
805760572 37898605
206735694 169104463
278383528 355075291
238806822 283935898
590873178 446404279
403785632 444803128
327998240 405933757
765596692 272894146
527142576 457420696
194319074 40442080
208239930 177472858
759287872 28844...

output:

70051
74989
70051
660170
620042
413427
780979
660170
413427
620042
70051
620042
660170
620042
620042
660170
660170
620042
620042
620042
70051
660170
70051
620042
413427
660170
679893
569144
620042
660170
620042
70051
660170
70051
660170
620042
679893
620042
251436
588867
251436
660170
660170
679893
...

result:

ok 300000 queries

Test #58:

score: 0
Accepted
time: 494ms
memory: 23888kb

input:

800000
859533899 327603466
851289878 336683992
876400955 306639541
591665207 453328054
959458490 8337028
921461738 225310183
422223389 454818562
958886141 32083630
79088063 226664203
953797097 95653528
48485471 112129198
107408054 282698995
228135032 398545966
168306428 355789126
949788818 122848741...

output:

-1
-1
628786
425363
-1
43479
-1
-1
94145
348981
-1
663730
-1
515689
780158
-1
-1
129356
-1
466895
-1
-1
118786
416460
-1
347055
331187
-1
287157
-1
612268
42733
-1
-1
-1
155752
555622
633498
207209
413473
164320
-1
331363
126606
-1
-1
-1
293370
122209
275746
637169
174468
271456
-1
449204
676346
232...

result:

ok 300000 queries

Test #59:

score: 0
Accepted
time: 468ms
memory: 22892kb

input:

800000
562323617 144714102
519118500 152170180
420817041 138559378
637109217 82772283
625699939 101897203
364847052 86683695
467069436 150816840
616415019 112944366
364663264 86330245
374592794 102293891
456788435 149234789
438903897 145075132
580187050 138113766
347406498 17842146
598689659 1278551...

output:

520211
81692
656591
-1
8596
-1
-1
322324
671267
240170
653988
-1
186790
45678
-1
410267
247862
-1
-1
771819
432372
-1
-1
-1
-1
171218
-1
-1
-1
-1
-1
95410
662169
506322
-1
-1
75088
670737
253959
223058
-1
-1
71576
432471
149097
-1
771669
53016
-1
381482
-1
350304
525953
-1
-1
-1
-1
783582
791699
-1
...

result:

ok 300000 queries

Test #60:

score: 0
Accepted
time: 513ms
memory: 23412kb

input:

800000
942756512 52543924
44606774 27253318
536381699 152557131
43053236 21652509
908162630 84923465
932345795 65063433
955505426 26892791
184184135 123045270
50861096 42198411
874591718 103020582
129816644 104926195
137604293 108095080
197493518 126366707
900724946 89610039
227731463 132772548
8126...

output:

4411
778200
471585
594592
476392
659458
-1
-1
72755
732976
566755
44062
295553
-1
748218
180738
785560
629341
-1
691647
-1
220341
-1
-1
-1
297571
-1
200730
507169
-1
-1
-1
327312
-1
-1
300045
120889
704921
-1
-1
174161
-1
432406
-1
-1
47829
370200
526917
-1
119722
500523
-1
696752
679796
-1
-1
23831...

result:

ok 300000 queries

Test #61:

score: 0
Accepted
time: 532ms
memory: 23524kb

input:

800000
795839484 153301438
429074202 451427452
443716494 454140505
498466270 458418625
770201744 260350057
196131196 77723965
294429446 374847478
793911864 165371065
738981738 328811518
436369790 452872345
244166796 296308363
195403854 65605399
510419398 458286268
311913826 392521549
281041900 35866...

output:

730419
-1
664866
-1
122704
-1
-1
-1
75622
-1
-1
597118
622634
165027
618897
-1
-1
-1
-1
493157
425417
-1
-1
-1
264570
245144
686959
-1
-1
773229
-1
489627
184970
-1
55353
421000
-1
684697
720163
34840
418334
429292
-1
93544
-1
-1
-1
-1
-1
-1
-1
612043
-1
380607
435643
-1
-1
597257
546540
548626
1043...

result:

ok 300000 queries

Extra Test:

score: 0
Extra Test Passed