QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#372192#7524. A Challenge For a TouristRobeZH#AC ✓659ms105032kbC++234.4kb2024-03-31 03:28:212024-03-31 03:28:22

Judging History

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

  • [2024-03-31 03:28:22]
  • 评测
  • 测评结果:AC
  • 用时:659ms
  • 内存:105032kb
  • [2024-03-31 03:28:21]
  • 提交

answer

#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
// #include<atcoder/all>
#define FR(i,n) for(int i=0;i<n;++i)
#define eb emplace_back
#define st first
#define nd second
#define x1 fxxkcjb
#define y1 fxxkyzc
#define x2 fxxkzzy
#define y2 fxxknitit
using namespace std;
namespace R=ranges;
template<typename T>
using func=function<T>;
template<typename T>
using vec=vector<T>;
using ll=long long;
using ld=long double;
using i128=__int128;
using pii=pair<int,int>;
const int mod=998244353;
struct E{
    int u,v,w;
};
int getbig(int x){
    assert(x>0);
    return 1<<(31-countl_zero(unsigned(x)));
}
struct GS{
    vector<int>bs;
    int clr(int val){
        for(int b:bs)if(val&getbig(b))val^=b;
        return val;
    }
    int add(int val){
        val=clr(val);
        if(!val)return val;
        for(int&b:bs)if(b&getbig(val))b^=val;//not needed, but is cleaner
        bs.eb(val);
        return val;
    }
};
struct SETS{
    unordered_set<int>a1,a2;
    void add(int x){
        if(a1.contains(x))a2.emplace(x),a1.erase(x);
        else a1.emplace(x);
    }
    void merge(SETS&s){
        for(int x:s.a1)add(x);
        for(int x:s.a2)a2.emplace(x);
    }
};
void sol(){
    int n,m;cin>>n>>m;
    vector<E>a(m);
    for(E&e:a)cin>>e.u>>e.v>>e.w,--e.u,--e.v;
    R::sort(a,[](E a,E b){return a.w<b.w;});
    vector<int>fa(n,-1),hsh(n,0);
    vector<GS>gss(n);
    vector<SETS>ques(n);
    func<int(int)>f=[&](int x){
        if(fa[x]==-1)return x;
        int nxt=fa[x];
        fa[x]=f(fa[x]);
        hsh[x]^=hsh[nxt];
        return fa[x];
    };
    int Q;cin>>Q;
    vector<int>orix(Q),oriy(Q),h(Q),ans(Q,-1);
    FR(i,Q){
        int x,y,z;cin>>x>>y>>z,--x,--y;
        ques[x].add(i);ques[y].add(i);
        orix[i]=x,oriy[i]=y,h[i]=z;
    }
    for(E e:a){
        int x=f(e.u),y=f(e.v);
        int neww=e.w^hsh[e.u]^hsh[e.v];
        if(x==y){
            if(int val=gss[x].add(neww)){
                // cerr<<val<<endl;
                vector<int>rmov;
                int bg=getbig(val);
                // cerr<<bg<<"b"<<endl;
                for(int q:ques[x].a2){
                    // cerr<<'h'<<q<<" "<<h[q]<<endl;
                    if(h[q]&bg){
                        h[q]^=val;
                        if(!h[q]){
                            ans[q]=e.w;
                            rmov.eb(q);
                        }
                    }
                }
                for(int q:rmov)ques[x].a2.erase(q);
            }
        }else{
            fa[x]=y;
            hsh[x]=neww;
            //merge gss
            auto sidework=[&](int x,int y){
                vector<int>tmp;
                for(int val:gss[x].bs)
                    if(int nv=gss[y].add(val))
                        tmp.eb(nv);
                if(!tmp.empty()){
                    for(int val:tmp){                 
                        vector<int>rmov;
                        int bg=getbig(val);
                        for(int q:ques[y].a2){
                            if(h[q]&bg){
                                h[q]^=val;
                                if(!h[q]){
                                    ans[q]=e.w;
                                    rmov.eb(q);
                                }
                            }
                        }
                        for(int q:rmov)ques[y].a2.erase(q);
                    }
                }
            };
            sidework(x,y);sidework(y,x);
            if(ques[y].a1.size()<ques[x].a1.size())swap(ques[y].a1,ques[x].a1);
            if(ques[y].a2.size()<ques[x].a2.size())swap(ques[y].a2,ques[x].a2);
            for(int q:ques[x].a1)if(ques[y].a1.contains(q)){
                f(orix[q]);f(oriy[q]);
                h[q]^=hsh[orix[q]]^hsh[oriy[q]];
                h[q]=gss[y].clr(h[q]);
                if(!h[q]){
                    ans[q]=e.w;
                }else{
                    ques[y].a2.emplace(q);
                }
            }else ques[y].a1.emplace(q);
            for(int q:ques[x].a2)ques[y].a2.emplace(q);
            //check ques e2
            //merge ques
        }
    }
    FR(i,Q)cout<<ans[i]<<"\n";
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    sol();
    return 0;
}
/*
6 6
5 6 3
6 2 2
1 2 1
2 3 2
2 4 3
4 5 1
5
1 3 1
1 3 3
1 3 5
2 6 4
2 4 0
*/

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3504kb

input:

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

output:

-1
2
4

result:

ok 3 number(s): "-1 2 4"

Test #2:

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

input:

2 1
1 2 1
1
1 2 1

output:

1

result:

ok 1 number(s): "1"

Test #3:

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

input:

5 10
1 2 4
2 2 0
1 1 7
2 1 7
4 1 1
5 5 1
4 1 4
5 2 6
1 1 2
2 4 7
10
1 4 3
1 2 5
3 2 1
3 5 5
2 4 0
3 2 0
2 1 2
2 3 6
5 1 7
2 3 3

output:

2
6
-1
-1
4
-1
6
-1
6
-1

result:

ok 10 numbers

Test #4:

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

input:

10 20
3 5 667
2 5 71
2 9 47
7 9 941
9 1 564
2 1 892
7 1 627
2 2 989
8 9 978
1 3 936
1 1 807
8 4 564
6 9 518
5 4 896
2 9 607
3 9 453
1 3 402
10 8 935
7 3 826
1 6 707
40
3 10 164
2 10 248
5 6 708
5 9 764
1 9 711
3 8 377
9 1 640
7 1 554
3 1 504
4 9 761
1 8 111
5 8 296
4 2 97
10 4 896
5 1 232
5 8 154
7 ...

output:

-1
941
-1
-1
-1
941
941
936
892
-1
896
-1
896
-1
-1
896
-1
941
-1
936
936
936
941
941
892
-1
-1
941
826
-1
896
-1
-1
936
896
-1
941
941
941
941

result:

ok 40 numbers

Test #5:

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

input:

20 40
11 3 622
15 1 463
1 13 754
10 16 87
17 16 602
19 4 1003
4 5 50
1 12 598
13 11 600
8 12 26
8 3 325
18 17 329
9 15 961
12 6 110
8 12 756
8 6 415
19 11 159
8 6 595
6 6 32
10 15 573
18 9 659
2 16 685
11 15 881
10 11 614
20 8 941
12 17 473
12 20 796
17 12 881
13 4 870
5 1 76
19 3 191
17 8 698
7 20 ...

output:

685
796
685
659
614
622
796
685
615
685
622
-1
-1
622
622
622
622
796
685
614
622
622
796
602
685
615
615
796
-1
622
796
685
659
614
685
659
614
685
685
685
685
659
-1
685
685
685
685
796
685
685
-1
685
598
796
685
796
796
622
-1
685
685
622
685
622
622
615
622
685
-1
-1
-1
685
796
615
615
796
685
7...

result:

ok 80 numbers

Test #6:

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

input:

30 60
20 6 610
28 8 847
1 9 442
30 5 574
5 23 49
12 17 415
3 24 116
3 22 164
3 16 464
27 1 179
19 11 689
16 8 840
12 28 242
13 14 300
20 21 243
6 7 50
10 28 207
27 2 858
5 17 164
27 19 839
28 25 399
10 11 185
6 10 157
24 8 309
2 22 722
5 4 688
13 19 314
10 15 858
13 22 286
12 24 376
29 17 37
7 4 762...

output:

526
513
513
513
464
526
442
513
526
513
526
526
526
526
513
376
513
526
526
526
513
513
526
513
498
526
464
526
498
394
526
526
526
526
526
526
498
526
526
526
526
526
526
526
442
498
526
513
526
526
513
526
513
526
513
526
513
513
513
376
526
442
513
513
513
415
464
415
498
513
526
498
498
464
513
...

result:

ok 120 numbers

Test #7:

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

input:

40 80
12 19 34
3 23 7
2 6 779
20 14 464
14 38 950
39 1 46
14 13 18
17 16 736
4 35 816
9 13 507
27 38 18
1 3 905
29 9 628
3 32 740
37 3 410
23 33 428
19 8 69
38 34 501
35 31 446
9 7 831
34 21 33
14 7 133
9 24 545
18 9 247
20 6 10
19 24 176
4 30 780
14 15 108
1 10 263
17 38 748
38 2 894
36 28 556
2 7 ...

output:

556
545
412
-1
-1
464
545
556
464
545
464
556
-1
295
545
424
556
545
545
365
464
545
556
556
412
556
412
464
464
556
545
464
545
464
-1
556
556
464
464
424
-1
410
-1
-1
-1
556
545
295
464
545
556
412
464
545
464
545
-1
545
-1
295
545
545
464
545
-1
545
-1
556
558
410
-1
464
545
464
464
-1
-1
424
-1
...

result:

ok 160 numbers

Test #8:

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

input:

50 100
33 19 845
50 31 685
27 25 461
15 36 18
17 35 853
49 32 539
7 6 840
24 8 1013
26 31 438
25 29 943
7 17 547
9 4 976
43 50 94
10 23 938
46 47 649
13 6 894
42 20 854
16 27 51
17 4 690
6 18 456
37 8 44
12 35 681
18 43 306
47 24 882
38 46 91
27 29 998
13 22 894
31 18 1010
42 27 165
9 2 75
6 19 588
...

output:

512
674
-1
701
544
541
572
572
572
674
572
572
541
572
544
544
544
588
853
572
572
572
572
572
572
539
572
572
572
544
-1
572
541
572
544
572
572
541
572
674
544
588
588
544
588
544
572
853
572
507
572
674
714
674
572
714
853
732
572
732
572
512
588
541
544
572
544
714
572
572
-1
853
541
544
541
572...

result:

ok 200 numbers

Test #9:

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

input:

60 120
34 41 6
4 31 444
54 5 918
58 8 474
6 44 453
43 52 497
43 59 354
25 40 189
26 23 273
19 42 977
6 1 296
55 56 716
22 21 116
22 46 392
52 7 103
10 26 502
60 39 358
14 20 646
48 4 772
17 29 759
11 40 781
3 8 637
21 46 886
28 21 181
7 48 425
36 40 2
43 33 803
59 21 859
36 28 548
4 9 951
57 13 170
...

output:

525
611
386
-1
524
679
562
474
611
525
386
525
-1
951
735
386
611
358
591
386
425
340
764
524
524
918
591
386
525
764
524
524
525
524
524
525
611
951
524
524
524
951
524
735
386
918
591
951
525
386
524
525
-1
348
764
524
951
524
524
524
-1
764
386
525
759
340
951
679
759
951
386
524
524
716
358
524
...

result:

ok 240 numbers

Test #10:

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

input:

70 140
14 56 377
66 1 557
34 54 500
21 55 342
70 3 452
21 16 1004
37 59 623
54 39 1001
32 32 964
63 59 208
57 7 785
46 24 324
23 39 724
9 54 482
21 21 734
54 46 197
19 56 222
63 45 731
6 18 56
7 33 582
10 68 40
29 18 276
3 32 651
25 43 920
47 6 404
39 62 946
56 49 839
35 57 168
2 49 367
12 6 442
42 ...

output:

594
539
539
539
635
450
539
472
490
539
525
594
539
539
543
539
539
920
539
696
582
472
472
539
450
594
539
573
543
573
649
472
594
490
573
539
539
464
543
450
519
472
635
539
453
539
472
519
472
543
525
539
450
644
644
482
696
594
635
444
539
644
539
543
412
920
594
519
453
539
594
490
519
450
539
...

result:

ok 280 numbers

Test #11:

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

input:

80 160
29 67 324
31 48 232
75 20 778
18 21 597
49 39 197
42 77 854
29 70 689
45 22 63
10 4 782
27 28 141
5 71 626
23 9 151
37 62 844
63 19 984
44 80 982
68 9 99
75 62 138
41 32 230
20 13 611
35 71 916
47 26 436
45 73 748
30 75 64
29 9 861
17 8 840
59 73 230
17 6 204
75 59 608
47 41 444
43 79 703
63 ...

output:

844
515
664
603
448
664
953
515
515
626
515
515
603
953
515
844
515
515
508
935
459
635
515
448
736
-1
515
576
448
844
515
878
515
576
576
-1
576
664
501
459
501
515
515
664
626
736
515
515
501
953
501
501
515
703
635
523
635
515
664
501
459
626
576
703
935
878
603
635
844
515
515
501
783
454
523
50...

result:

ok 320 numbers

Test #12:

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

input:

90 180
82 2 648
85 65 932
10 78 136
48 6 670
69 21 697
55 50 763
71 60 455
62 20 665
74 12 173
89 27 750
19 38 83
47 24 152
66 73 370
84 22 941
6 12 571
74 37 568
20 37 954
5 74 998
86 48 986
29 64 32
53 57 693
9 73 69
39 49 765
32 45 997
49 50 543
51 46 790
65 87 255
50 65 480
23 87 732
27 35 220
1...

output:

699
514
568
514
514
720
568
648
648
665
699
480
665
528
528
464
514
948
699
461
699
514
720
528
600
871
528
600
699
571
611
514
790
871
528
665
514
1021
720
492
790
699
720
480
699
597
528
665
528
699
528
568
514
528
699
1021
571
699
699
568
699
514
568
568
599
492
790
528
528
528
699
568
720
514
61...

result:

ok 360 numbers

Test #13:

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

input:

100 200
6 45 162
46 33 419
18 88 669
75 4 966
64 3 262
66 35 479
30 76 952
20 80 734
28 48 51
28 64 307
46 24 566
23 89 429
14 66 609
73 15 344
81 82 880
100 67 724
60 14 596
98 17 417
32 24 731
72 12 163
70 66 216
8 7 852
43 16 776
100 75 760
39 18 726
6 66 278
45 71 691
84 58 1011
58 88 892
28 71 ...

output:

528
514
720
609
581
429
468
514
528
528
528
429
528
552
528
479
514
691
514
517
585
514
585
806
585
528
585
434
528
514
528
514
528
720
552
552
609
528
514
528
528
479
528
517
344
514
417
528
609
528
446
806
806
528
528
-1
550
434
806
691
550
528
806
609
528
479
552
514
552
528
806
514
514
-1
514
60...

result:

ok 400 numbers

Test #14:

score: 0
Accepted
time: 464ms
memory: 96976kb

input:

200000 200000
109342 177585 227729360
47204 185227 65000004
18413 107067 731586911
193618 193271 176899956
193975 45521 123073233
21309 181614 329804012
138160 118319 203452859
124884 8693 566070106
159912 46179 902860088
166651 68050 474901516
186453 75667 211242475
128492 19333 1063841125
15161 12...

output:

-1
-1
867002222
756893127
893777656
794446704
1047710880
928938116
665867444
756355523
619390985
-1
921982297
-1
-1
-1
-1
984785973
693903984
683706666
845743685
-1
646184093
934291503
873911518
616673597
830156759
-1
676344238
818209218
-1
959609719
-1
830776927
720735705
-1
969168009
829364544
-1
...

result:

ok 200000 numbers

Test #15:

score: 0
Accepted
time: 445ms
memory: 96432kb

input:

200000 200000
87 159493 1004393170
21352 10917 196334107
58787 62730 943561852
29814 80998 892175899
106351 98220 532814271
179725 112396 746992581
188089 8377 685730287
73722 68193 194367885
192153 5848 706209688
36993 27859 427824942
165200 100710 810280288
45066 141749 232346113
92544 77436 74624...

output:

-1
725561349
-1
-1
1041814832
-1
566535611
-1
847790168
-1
801117050
767199268
-1
897632551
-1
694156002
1028718162
851852574
778415440
837247383
-1
925715962
-1
617554679
947622426
797075601
732345765
581795607
581395898
-1
1054670730
714012171
927590703
843385218
-1
594420845
811897992
705988900
7...

result:

ok 200000 numbers

Test #16:

score: 0
Accepted
time: 525ms
memory: 96824kb

input:

200000 200000
198494 165643 575324511
181016 66449 1065322153
165181 143397 24581834
143391 198983 9866629
179665 194682 497649408
90640 194984 613451737
167407 18673 628528759
199136 142368 576713736
171940 179822 826229364
105815 77923 304986038
54646 16951 161446326
72319 20628 692179685
24524 13...

output:

1034511907
857626129
-1
-1
630373350
878226623
-1
770204552
-1
-1
750734050
-1
680993075
-1
937880944
622514993
-1
-1
-1
629784547
862196200
-1
666733467
715120680
980307839
718824125
622193052
802260393
794996087
654935584
952736251
710294889
997845249
-1
743687945
-1
1044320027
574705974
-1
-1
624...

result:

ok 200000 numbers

Test #17:

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

input:

200000 200000
181419 149800 722194190
184899 30233 406526416
12627 184368 461819352
50406 184138 56072711
36649 146020 11103399
58305 63525 1054497174
65445 111320 294974203
28050 122695 823135923
13527 81202 641920496
117506 29016 68060418
135134 92575 582554935
82301 181136 404220218
106083 119484...

output:

569288751
831434641
-1
920862069
979288812
747342841
647773540
698123047
-1
943985851
683746818
-1
620927288
659909725
661858842
-1
683959261
-1
-1
-1
730409534
-1
871186574
-1
598350740
-1
-1
1010240795
933657223
745412390
905357550
871574299
648279218
-1
742171929
-1
-1
-1
594628096
-1
613752538
6...

result:

ok 200000 numbers

Test #18:

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

input:

200000 200000
44161 78677 608279087
88995 53260 981544094
146705 177900 534397056
21607 144362 39446700
155677 104939 773366612
60554 3880 936090968
10726 134856 868155296
81383 129346 677461739
10580 137609 748717579
89496 66945 47831733
13395 163913 1022791866
921 66884 729817045
183045 3368 29298...

output:

-1
584622481
820541910
-1
854155129
790994153
999729010
654981781
940073167
903255303
995576344
-1
-1
678814274
-1
1026097915
-1
-1
655155315
709024139
630356732
921141385
-1
641608685
763652771
-1
738774378
747978959
-1
-1
694241664
663894145
-1
814509249
960285895
1029364395
807730051
-1
705849960...

result:

ok 200000 numbers

Test #19:

score: 0
Accepted
time: 509ms
memory: 96812kb

input:

200000 200000
50621 23085 799318104
169569 2113 488786657
56313 136715 144934133
19820 34052 763518186
116851 157271 258218883
18302 196537 1034089281
144015 109808 333489262
30315 62782 611603377
135977 52103 767929284
28680 172928 78682125
134933 74616 770607930
71492 187418 287070180
159778 83817...

output:

-1
-1
-1
812630173
-1
847390275
-1
949031773
1064718647
-1
-1
689565788
837528029
622816397
974081560
887226865
-1
751230044
957884451
-1
-1
887281377
702502518
679545644
626540089
594378110
635582388
742932582
571842692
1023438234
762729206
898407139
-1
792391889
-1
-1
861339430
-1
-1
696630325
759...

result:

ok 200000 numbers

Test #20:

score: 0
Accepted
time: 659ms
memory: 105032kb

input:

100000 200000
41586 4424 697628463
81874 32727 208545646
26932 64908 1047751949
9726 59915 296089205
55006 21898 526800356
34083 66394 241951281
87192 40916 894678925
9183 84409 293533088
3387 83932 275770761
66353 38672 521187462
11306 52107 195091056
30776 66998 951473510
17009 10252 373626096
169...

output:

706479056
796570207
445303222
710407692
833479688
662355681
15569184
345554721
908977568
45999363
463292219
309520961
857093307
1073710164
864568445
517049595
826679496
811154941
266781591
962897393
643219087
796800215
776180302
680232756
501930828
976337957
867145367
857945302
1073683682
893884404
...

result:

ok 200000 numbers

Test #21:

score: 0
Accepted
time: 217ms
memory: 51620kb

input:

110000 187585
23693 23693 260328316
40017 40017 717849382
76058 76058 345207845
5941 5941 973620527
74929 52756 132156947
46284 46284 110519088
52066 52066 318618469
83388 41304 575280127
4148 4148 308823289
31813 31813 819265914
52574 52574 464610702
85712 85712 594912755
57980 57980 715289602
4846...

output:

-1
-1
-1
-1
-1
-1
-1
-1
982852221
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
784874877
-1
-1
622037727
829448916
-1
-1
971099102
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
676741976
-1
-1
84122119
-1
258524673
851307700
-1
-1
-1
227041043
-1
-1
-1
6466066
-1
-1
-1
-1
606413750
-1
-1
-1
-1
-1
-1
...

result:

ok 187585 numbers

Test #22:

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

input:

120000 157963
13010 13010 591417088
9861 9861 620650301
93208 93208 37890427
107309 107309 856767877
4841 4841 787590669
77765 77765 63516790
82372 82372 331101147
92362 92362 587628783
49180 49180 481813350
109909 109909 236720887
35959 35959 759588545
27704 27704 611701950
96701 96701 769172731
72...

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
750010032
-1
-1
324111713
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1006614616
-1
-1
641263513
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
926915009
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 157963 numbers

Test #23:

score: 0
Accepted
time: 290ms
memory: 62788kb

input:

130000 192084
86538 86538 874548688
33144 62295 775596530
17017 17017 244289422
3693 4593 758037079
102443 40730 499644950
21496 21496 395379125
92791 103683 916000668
13765 13765 640962394
41498 2592 162403493
123890 99930 197456048
48793 71546 902353306
22206 22206 452920051
114921 24437 150946796...

output:

702395897
72145842
99604830
-1
-1
427210678
407030613
260253724
1045545089
560488259
513877080
-1
614376204
625375721
-1
81813949
-1
1027121529
-1
431253808
866161920
-1
210183864
977103891
274754544
154995486
473187706
-1
386545407
219713047
655374672
392027077
703895480
149080597
700000200
2283593...

result:

ok 192084 numbers

Test #24:

score: 0
Accepted
time: 236ms
memory: 60148kb

input:

140000 176204
65376 65376 1028064266
19771 90515 878833054
105136 76429 135953113
75169 69211 376168990
65718 114589 323501713
29108 31149 948963783
53348 53348 93371590
12292 89441 1013528906
31988 28892 948262432
122679 53720 654657391
79137 79137 327732460
27150 77535 7479827
117090 117090 590992...

output:

-1
91695842
-1
1072645411
-1
989243311
528596959
548338498
-1
428937247
124931964
-1
-1
-1
261732347
-1
-1
861544067
-1
-1
-1
408611658
15637088
897780261
826187544
627399306
684388859
-1
665737530
438039641
352216189
245567184
-1
535538282
-1
-1
-1
673898224
-1
829234398
895582909
-1
959535788
1027...

result:

ok 176204 numbers

Test #25:

score: 0
Accepted
time: 245ms
memory: 62312kb

input:

150000 191723
60958 48382 506073494
115490 115490 613984068
6445 6445 904345931
116322 116322 473345203
93164 93164 225385764
78513 83320 214801600
105818 105818 797637676
54442 147123 87337901
130241 130241 220314537
33845 5571 367406727
102082 59953 730208587
145584 145584 351343892
54077 54077 32...

output:

-1
-1
-1
378448195
-1
566535791
852978490
-1
-1
1019622166
-1
679204997
-1
-1
-1
913831333
-1
-1
-1
182487140
-1
-1
465537899
614623361
704640058
-1
-1
-1
-1
570562033
176037425
673115932
-1
84052876
-1
-1
710474201
-1
100852295
-1
-1
670183326
196374133
982511418
-1
-1
-1
335001712
-1
-1
-1
5895680...

result:

ok 191723 numbers

Test #26:

score: 0
Accepted
time: 292ms
memory: 67956kb

input:

160000 175843
149258 91345 121217762
141545 15575 313462396
150778 108103 513023667
87461 100025 1043452531
11145 151603 681276991
6303 24370 733293126
33000 33000 5667183
11935 6640 794238421
81626 40228 809250484
65922 65922 464064029
83523 87801 701438153
48106 30039 107190454
7149 9327 929964961...

output:

546649649
797518618
872460490
413930609
854773235
119648686
782069118
132268245
272055226
977483671
703718991
289155075
930718536
-1
457179186
437412118
519172401
256813169
100664549
766809922
389579432
986988061
665112035
845436100
-1
595658993
245637618
822735806
1035906276
774746740
54900390
5214...

result:

ok 175843 numbers

Test #27:

score: 0
Accepted
time: 250ms
memory: 65868kb

input:

170000 159964
73910 81276 90183505
107899 19484 210894288
133053 133053 699350234
105418 124580 576665443
52835 157518 359041865
104062 127961 749172598
96869 7390 377479836
163888 88656 926913391
69524 27918 337717645
105914 146164 766978916
53592 24169 558867234
8203 149774 164508526
50840 78409 2...

output:

571486043
-1
546680631
760191679
386679482
957001255
260751507
42709042
405288183
255874392
685971806
353975615
212064408
-1
882764013
870898775
867332084
936818351
342204532
-1
728573419
124552759
420389295
764553776
440417549
129677110
521676120
1011105275
-1
313394926
59967058
655641434
-1
922994...

result:

ok 159964 numbers

Test #28:

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

input:

180000 194085
11114 11114 827265831
164474 111250 718600578
111685 111685 94367111
163799 163799 842132447
137765 137765 1001023618
119023 119023 107931024
40872 40872 201676153
140651 5369 8499149
77483 77483 307058366
158825 158825 200100346
134564 134564 175636512
148209 148209 1044942754
171406 ...

output:

-1
156118328
-1
-1
365953067
-1
-1
329688466
-1
-1
604835796
1022163491
-1
221539042
393702501
-1
-1
-1
-1
712981227
526818792
1041823763
-1
-1
-1
-1
32141994
329649937
-1
545206010
-1
638328158
821984824
-1
39908755
-1
153254669
-1
-1
-1
-1
-1
-1
-1
968179320
88320478
-1
-1
-1
-1
-1
-1
580053395
-1...

result:

ok 194085 numbers

Test #29:

score: 0
Accepted
time: 236ms
memory: 67232kb

input:

190000 164463
62571 34777 896876064
111874 111874 438003059
150172 148535 738069714
2089 100134 595189640
128538 163263 1007449887
142611 126848 706959845
45428 45428 774310434
40107 40107 850208491
16794 63343 1072548477
58851 128239 172831056
94685 186673 954255784
13928 93485 339338714
37874 3787...

output:

557476195
-1
672943255
-1
374624679
289986746
-1
879915378
-1
-1
979151772
442009803
-1
681347100
657041740
-1
-1
-1
679691230
550720428
-1
879472003
-1
999209688
167999132
-1
1039665392
-1
-1
-1
494272760
292426391
-1
291318574
844385108
305602217
839672990
512150752
-1
-1
-1
418777187
-1
-1
-1
-1
...

result:

ok 164463 numbers

Test #30:

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

input:

200000 164443
86136 58617 423675455
4590 45193 325177905
129516 35839 446384631
180314 180314 540065528
167297 123694 68290106
134121 174065 796223221
127351 59018 612051986
62959 123335 351293941
50045 15133 592116369
163872 172640 958111857
33009 165864 106055980
74104 154008 159958151
142980 7522...

output:

-1
626760387
-1
806728558
16613352
891755096
674521156
403857182
571227425
492029315
864532640
5370067
295375690
38664282
776407076
146711939
909718418
520450081
675229288
798697856
369171310
387673047
380187900
502525484
268269150
891847813
820373637
873643252
686027135
631187506
571582402
57025905...

result:

ok 164443 numbers