QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#136169#2415. Firetrucks Are RedBUET_TEAM_ONE#AC ✓114ms25460kbC++142.3kb2023-08-07 14:58:572023-08-07 14:58:58

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-07 14:58:58]
  • 评测
  • 测评结果:AC
  • 用时:114ms
  • 内存:25460kb
  • [2023-08-07 14:58:57]
  • 提交

answer

#include <bits/stdc++.h>
typedef long long int ll;
#define endl            '\n'
#define pb             push_back
#define mp              make_pair
#define pll             pair<ll,ll> 
#define fill(x, y)     memset(x, y, sizeof(x))
#define all(x)         (x).begin(), (x).end()
#define debug(x)       { cerr << #x << " = " << x << endl; }
#define IO	       { ios_base::sync_with_stdio(false); cin.tie(0); }
#define read(x)	       freopen(x, "r", stdin)
#define write(x)       freopen(x, "w", stdout)
#define N       1000000

using namespace std;

typedef vector<int> vi;



struct DSU {
    vi Arr, sz;
 
    int root (int i)
    {
        while(Arr[ i ] != i)
        {
            Arr[i] = Arr[ Arr[i] ] ; 
            i=Arr[i]; 
        }
        return i;
    }
    
    DSU(int n)
    {
        Arr = vi(n+5);
        sz = vi(n+5);
        for(int i = 0;i<n;i++)
        {
            Arr[i] = i ;
            sz[i] = 1;
        }
    }
    
    void Union(int A,int B)
    {
        int root_A = root(A);
        int root_B = root(B);
        if(sz[root_A] < sz[root_B ])
        {
            Arr[ root_A ] = Arr[root_B];
            sz[root_B] += sz[root_A];
        }
        else
        {
            Arr[root_B] = Arr[root_A];
            sz[root_A] += sz[root_B];
        }
    
    }
 
};

void solve() {
    int n;
    cin >> n;
    map<int, vector<int>> mp;

    for (int i=1; i<=n; i++) {
        int m;
        cin >> m;
        for (int j=0; j<m; j++) {
            int x;
            cin >> x;
            mp[x].pb(i);
        }
    }
    DSU dsu(n+100);

    vector<vi> connects;

    for (auto &k: mp) {
        int col = k.first;
        for (int i=1; i<k.second.size(); i++) {
            // try to connect k.second[i] and k.second[i-1]
            if (dsu.root(k.second[i]) != dsu.root(k.second[i-1])) {
                dsu.Union(k.second[i], k.second[i-1]);
                connects.push_back({k.second[i], k.second[i-1], col});
            }
        }
    }
    if (connects.size() != n-1) {
        cout << "impossible" << endl;
    }
    else {
        for (vi x: connects) {
            cout << x[0] << " " << x[1] << " " << x[2] << endl;
        }
    }
}


int main() {
    IO;
    //cout << fixed << setprecision(10);
    solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2
1 144272510
1 144272510

output:

2 1 144272510

result:

ok 

Test #2:

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

input:

2
3 926756583 60721576 911666163
1 926756583

output:

2 1 926756583

result:

ok 

Test #3:

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

input:

10
2 853832590 668835602
1 668835602
1 384974576
2 274281999 796487719
3 668835602 384974576 853832590
3 274281999 796487719 668835602
4 668835602 274281999 853832590 384974576
2 796487719 274281999
1 384974576
1 274281999

output:

6 4 274281999
7 6 274281999
8 7 274281999
10 8 274281999
5 3 384974576
7 5 384974576
9 7 384974576
2 1 668835602
5 2 668835602

result:

ok 

Test #4:

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

input:

100
2 342937749 285101060
2 579015745 292807338
3 456017432 101157443 285101060
1 280913935
2 859297027 444536025
2 504931657 783643441
2 456017432 360328443
2 655033009 977719989
2 23503993 86510939
1 280913935
3 882566438 400677901 280913935
4 285101060 711696014 782637467 655033009
1 504931657
1 ...

output:

impossible

result:

ok 

Test #5:

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

input:

20
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1

output:

2 1 1
3 2 1
4 3 1
5 4 1
6 5 1
7 6 1
8 7 1
9 8 1
10 9 1
11 10 1
12 11 1
13 12 1
14 13 1
15 14 1
16 15 1
17 16 1
18 17 1
19 18 1
20 19 1

result:

ok 

Test #6:

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

input:

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

output:

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

result:

ok 

Test #7:

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

input:

6
2 17 10
1 5
2 10 22
3 17 22 9
2 17 8
3 9 22 16

output:

impossible

result:

ok 

Test #8:

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

input:

6
2 17 10
2 5 10
2 10 22
3 17 22 9
2 17 8
3 9 22 16

output:

6 4 9
2 1 10
3 2 10
4 1 17
5 4 17

result:

ok 

Test #9:

score: 0
Accepted
time: 89ms
memory: 19904kb

input:

2
100135 50111079 636408060 792100042 5331285 336232714 372531348 162635402 202613385 334090836 434578373 974884818 991177868 34904916 852254962 932427235 990037224 28539707 529294723 999535479 92353517 160063080 301178333 783582003 898654302 448001960 798608014 499842001 640408898 149094210 9433621...

output:

2 1 9931

result:

ok 

Test #10:

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

input:

2
100205 402692425 947048076 726644125 19396699 862992483 245024640 740973675 980569112 910684526 801789052 557001194 245807612 61789671 812894241 226721911 929071642 127202795 669601395 762104667 274761931 736916240 633593859 295582544 557936950 541234480 853475793 409017481 571982228 320919975 148...

output:

2 1 2350

result:

ok 

Test #11:

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

input:

1000
1 170570389
1 876309004
1 270859704
1 681063235
3 388428750 214660301 173343388
2 230530420 459123744
2 425028352 430985812
2 888134465 613326043
3 937167878 531627138 892379916
1 66423869
1 427424009
1 86523514
3 353975089 939671730 250542715
1 297337445
1 681192098
3 581503268 664754894 49731...

output:

impossible

result:

ok 

Test #12:

score: 0
Accepted
time: 20ms
memory: 4660kb

input:

1000
196 353335732 409189874 700840930 330445933 481862392 520871605 16334747 286519743 757135435 336218173 371759648 246353297 587875214 775977271 277408406 445423784 897302904 144984294 159136901 239018567 120141137 815375811 768250891 370067413 169973067 147431809 135776656 669999566 368541780 47...

output:

5 1 489377
13 5 489377
17 13 489377
24 17 489377
30 24 489377
31 30 489377
33 31 489377
35 33 489377
46 35 489377
50 46 489377
56 50 489377
58 56 489377
64 58 489377
67 64 489377
76 67 489377
77 76 489377
83 77 489377
84 83 489377
88 84 489377
89 88 489377
90 89 489377
99 90 489377
110 99 489377
114...

result:

ok 

Test #13:

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

input:

1000
189 828192941 685817733 678017774 41116968 572481375 371245577 332259182 647183053 54592220 490654862 280198999 816286534 67217910 266490029 183296111 881325755 423521527 199040467 773986454 126627449 878841975 158056460 708000087 942344906 982273186 148549394 807148449 36561902 75342254 466857...

output:

73 48 184701
143 73 184701
196 143 184701
205 196 184701
218 205 184701
266 218 184701
281 266 184701
302 281 184701
397 302 184701
477 397 184701
517 477 184701
617 517 184701
630 617 184701
695 630 184701
736 695 184701
766 736 184701
782 766 184701
836 782 184701
971 836 184701
43 42 415498
50 43...

result:

ok 

Test #14:

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

input:

200000
1 338399905
1 776534810
1 145642942
1 204041132
1 903206281
1 97213556
1 623800194
1 274470932
1 462713477
1 427531118
1 161862854
1 601371719
1 852865573
1 843902403
1 255426727
1 621765222
1 171216106
1 786755429
1 779543103
1 912736055
1 692014287
1 942045680
1 770693979
1 898055070
1 2407...

output:

impossible

result:

ok 

Test #15:

score: 0
Accepted
time: 50ms
memory: 17604kb

input:

200000
1 485738844
1 485738844
1 485738844
1 485738844
1 485738844
1 485738844
1 485738844
1 485738844
1 485738844
1 485738844
1 485738844
1 485738844
1 485738844
1 485738844
1 485738844
1 485738844
1 485738844
1 485738844
1 485738844
1 485738844
1 485738844
1 485738844
1 485738844
1 485738844
1 485...

output:

2 1 485738844
3 2 485738844
4 3 485738844
5 4 485738844
6 5 485738844
7 6 485738844
8 7 485738844
9 8 485738844
10 9 485738844
11 10 485738844
12 11 485738844
13 12 485738844
14 13 485738844
15 14 485738844
16 15 485738844
17 16 485738844
18 17 485738844
19 18 485738844
20 19 485738844
21 20 4857388...

result:

ok 

Test #16:

score: 0
Accepted
time: 56ms
memory: 11208kb

input:

100000
4 66986508 25672697 741308508 398643872
4 810714430 462971176 784903561 135133396
2 341884150 214808229
1 994562898
2 914628988 214354925
4 65267068 652634200 116594039 329964803
1 854894070
3 542040307 780705654 222928058
2 11661309 901308589
1 659980722
3 468105719 928529221 222066733
2 245...

output:

712 223 1005458
1278 712 1005458
1543 1278 1005458
2375 1543 1005458
2909 2375 1005458
3487 2909 1005458
3750 3487 1005458
4019 3750 1005458
4430 4019 1005458
6889 4430 1005458
7074 6889 1005458
9470 7074 1005458
10076 9470 1005458
11509 10076 1005458
12495 11509 1005458
12935 12495 1005458
14656 12...

result:

ok 

Test #17:

score: 0
Accepted
time: 76ms
memory: 16700kb

input:

66666
2 117465641 402715707
1 341083455
3 796958965 710301355 746905126
2 163268728 402102113
4 84769750 669732542 277812555 545765863
3 671164754 815075092 771856917
4 25145580 417136497 804678582 122185977
2 158857856 778998238
5 562047347 598388755 863583758 326100092 736225275
3 515335420 622477...

output:

impossible

result:

ok 

Test #18:

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

input:

66666
4 167619805 562085576 20222422 415275945
1 511659696
2 224047708 571170368
3 120215750 94035264 97028106
5 276938180 521048020 802135121 911006466 705678159
4 252107501 453206228 740527965 914645729
3 400916347 283609115 668954016
3 35760649 532141113 616088838
1 248512755
4 298227773 22976291...

output:

impossible

result:

ok 

Test #19:

score: 0
Accepted
time: 61ms
memory: 11128kb

input:

66666
3 505166193 93395939 794797228
3 547883844 731355206 518083062
2 15213032 934919980
2 879180481 615561017
3 31298049 778588758 913384358
2 622135901 96045329
2 575635537 725226152
3 371764320 541399775 739118591
6 231117007 172771060 677274540 384078219 784517111 743815130
2 285841853 98779078...

output:

7281 5791 32011
10588 7281 32011
16938 10588 32011
18641 16938 32011
35153 18641 32011
37845 35153 32011
38597 37845 32011
39565 38597 32011
44282 39565 32011
46189 44282 32011
47733 46189 32011
48127 47733 32011
56282 48127 32011
56829 56282 32011
66633 56829 32011
6368 1250 79847
6487 6368 79847
1...

result:

ok 

Test #20:

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

input:

66666
4 749237116 132626332 124653400 339740401
5 902503400 337405919 65585420 185910494 837432922
3 291170815 632807307 121977500
4 751040039 296835194 206735974 984844966
3 111334746 262468099 785973792
2 205568802 86034642
3 309871088 609050508 660559706
4 517816127 592885374 401382439 973321939
...

output:

3842 3427 30954
4123 3842 30954
4626 4123 30954
5289 4626 30954
5684 5289 30954
6326 5684 30954
6393 6326 30954
7323 6393 30954
7954 7323 30954
8214 7954 30954
8839 8214 30954
9364 8839 30954
9565 9364 30954
10286 9565 30954
10700 10286 30954
10909 10700 30954
11051 10909 30954
11129 11051 30954
124...

result:

ok 

Test #21:

score: 0
Accepted
time: 35ms
memory: 10972kb

input:

66666
6 515669354 687383080 707128932 726182260 74279860 801435741
3 54358921 332000472 900808766
4 520645316 241523225 22184995 183316997
1 802646452
3 54358921 726182260 373470557
1 87900645
3 977149212 80562651 211060053
3 572446680 600105575 412500581
1 679788096
2 118549454 617308388
3 34239371...

output:

73 29 5538186
91 73 5538186
264 91 5538186
363 264 5538186
374 363 5538186
418 374 5538186
484 418 5538186
609 484 5538186
686 609 5538186
704 686 5538186
756 704 5538186
790 756 5538186
880 790 5538186
946 880 5538186
1047 946 5538186
1064 1047 5538186
1320 1064 5538186
1371 1320 5538186
1501 1371 ...

result:

ok 

Test #22:

score: 0
Accepted
time: 25ms
memory: 11228kb

input:

66666
5 710205641 257157154 674511470 131872120 212536025
5 525613093 131872120 481922738 257157154 194631666
1 359230746
3 525613093 212536025 257157154
3 359230746 257157154 710205641
5 481922738 359230746 525613093 257157154 194631666
3 359230746 212536025 525613093
2 131872120 525613093
2 257157...

output:

2 1 131872120
8 2 131872120
14 8 131872120
15 14 131872120
17 15 131872120
22 17 131872120
27 22 131872120
28 27 131872120
30 28 131872120
31 30 131872120
34 31 131872120
37 34 131872120
38 37 131872120
39 38 131872120
43 39 131872120
44 43 131872120
49 44 131872120
55 49 131872120
57 55 131872120
6...

result:

ok 

Test #23:

score: 0
Accepted
time: 78ms
memory: 15732kb

input:

50000
6 327676685 79137275 172885291 41826002 513900407 200386950
2 911586845 528189521
3 14558835 606854109 974795538
5 599278628 990072740 612558639 555435869 17559339
8 194313587 750835784 207940884 465375971 258158238 850965099 731439619 687176816
4 617462223 279393256 937673983 8864693
1 399356...

output:

impossible

result:

ok 

Test #24:

score: 0
Accepted
time: 66ms
memory: 13292kb

input:

50000
4 512682157 894833087 462054922 672207899
3 186079333 215371999 978545964
3 390642511 761179740 222727271
5 905506567 523166275 986970964 429848502 337309069
3 708115126 258594335 348461019
3 79395475 301162131 232119367
4 84645608 968578204 387392630 283880191
5 614472420 16828810 519408494 7...

output:

impossible

result:

ok 

Test #25:

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

input:

50000
7 459024596 704635913 923032689 888506127 355421029 816452434 533927184
4 11507956 754991312 655898369 362125251
5 402589851 499809379 319301087 625834427 897561803
6 750964819 437600356 724161830 160741809 381715968 170156679
1 783186878
3 258915852 395478803 373821424
1 55849302
5 92474652 8...

output:

impossible

result:

ok 

Test #26:

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

input:

50000
4 201187612 187117236 629403624 963202955
4 877506290 666252315 647721243 814417071
7 713202719 878716501 590716451 996553674 800640977 506610029 556291142
7 622849656 10540298 732705521 1437031 745954200 855866887 752624529
5 705212263 315649312 502466883 138595442 163565734
2 404721597 89829...

output:

4136 449 14384
7825 4136 14384
17673 7825 14384
22748 17673 14384
29437 22748 14384
30371 29437 14384
32555 30371 14384
32989 32555 14384
33539 32989 14384
40446 33539 14384
1438 111 32882
1490 1438 32882
7393 1490 32882
24155 7393 32882
26547 24155 32882
28951 26547 32882
34389 28951 32882
43596 34...

result:

ok 

Test #27:

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

input:

50000
8 641325023 789626607 492294335 504104914 686670938 629318609 3405465 937984260
3 483183626 330148255 304702304
4 35452084 394430004 574991316 273067480
4 292742571 330148255 355025841 858928228
2 871443606 47618503
8 810711155 457566975 952329071 180610816 887126652 533154325 123937219 111135...

output:

181 82 43812
353 181 43812
1132 353 43812
2547 1132 43812
4016 2547 43812
4032 4016 43812
4855 4032 43812
5102 4855 43812
5878 5102 43812
6317 5878 43812
6374 6317 43812
6377 6374 43812
8278 6377 43812
11675 8278 43812
12222 11675 43812
13860 12222 43812
13902 13860 43812
14766 13902 43812
15486 147...

result:

ok 

Test #28:

score: 0
Accepted
time: 29ms
memory: 7112kb

input:

50000
2 164209258 104050975
2 527540136 473925754
2 731917343 212682687
2 100496618 473925754
5 304267884 696839751 797559398 363923049 229489591
5 907542871 141034869 992839470 35711814 348169471
2 816640729 124117860
6 530886688 842539091 731917343 582060567 813613886 141034869
2 879556072 8166407...

output:

81 66 13649040
86 81 13649040
101 86 13649040
168 101 13649040
173 168 13649040
187 173 13649040
216 187 13649040
218 216 13649040
248 218 13649040
273 248 13649040
274 273 13649040
315 274 13649040
337 315 13649040
346 337 13649040
375 346 13649040
389 375 13649040
409 389 13649040
414 409 13649040...

result:

ok 

Test #29:

score: 0
Accepted
time: 16ms
memory: 7236kb

input:

50000
6 999625659 905741186 404760190 905644043 995131580 16469317
5 404760190 825156184 327224558 935989460 229829890
3 905644043 995131580 905741186
3 404760190 935989460 229829890
5 905644043 905741186 327224558 825156184 935989460
1 327224558
7 229829890 404760190 16469317 905741186 327224558 99...

output:

7 1 16469317
8 7 16469317
10 8 16469317
11 10 16469317
13 11 16469317
14 13 16469317
15 14 16469317
17 15 16469317
18 17 16469317
24 18 16469317
26 24 16469317
28 26 16469317
29 28 16469317
30 29 16469317
33 30 16469317
38 33 16469317
39 38 16469317
43 39 16469317
46 43 16469317
50 46 16469317
58 50...

result:

ok 

Test #30:

score: 0
Accepted
time: 20ms
memory: 7080kb

input:

50000
4 708119118 220287425 802397886 217703977
5 220287425 802397886 217703977 708119118 973596356
4 220287425 802397886 973596356 217703977
3 802397886 217703977 220287425
4 973596356 217703977 220287425 802397886
5 708119118 802397886 973596356 217703977 220287425
5 802397886 973596356 217703977 ...

output:

2 1 217703977
3 2 217703977
4 3 217703977
5 4 217703977
6 5 217703977
7 6 217703977
8 7 217703977
9 8 217703977
10 9 217703977
11 10 217703977
12 11 217703977
13 12 217703977
14 13 217703977
15 14 217703977
16 15 217703977
17 16 217703977
20 17 217703977
21 20 217703977
22 21 217703977
23 22 2177039...

result:

ok 

Test #31:

score: 0
Accepted
time: 85ms
memory: 21148kb

input:

100000
1 696318585
2 696318585 515269277
2 515269277 753089815
2 753089815 297661051
2 297661051 307064222
2 307064222 210886233
2 210886233 79402165
2 79402165 70189682
2 70189682 273165062
2 273165062 885039674
2 885039674 579352176
2 579352176 357627595
2 357627595 271562978
2 271562978 399834305...

output:

44969 44968 6547
31369 31368 6898
71756 71755 7219
63728 63727 7243
77642 77641 12704
82169 82168 17635
16903 16902 18401
77836 77835 22063
12933 12932 22145
21462 21461 25796
86695 86694 28201
22021 22020 44877
32789 32788 46810
63073 63072 47059
37841 37840 56968
6457 6456 67051
16437 16436 73341
...

result:

ok 

Test #32:

score: 0
Accepted
time: 63ms
memory: 20368kb

input:

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

output:

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

result:

ok 

Test #33:

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

input:

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

output:

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

result:

ok 

Test #34:

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

input:

100001
1 100000
2 99999 100000
2 99998 99999
2 99997 99998
2 99996 99997
2 99995 99996
2 99994 99995
2 99993 99994
2 99992 99993
2 99991 99992
2 99990 99991
2 99989 99990
2 99988 99989
2 99987 99988
2 99986 99987
2 99985 99986
2 99984 99985
2 99983 99984
2 99982 99983
2 99981 99982
2 99980 99981
2 9...

output:

100001 100000 1
100000 99999 2
99999 99998 3
99998 99997 4
99997 99996 5
99996 99995 6
99995 99994 7
99994 99993 8
99993 99992 9
99992 99991 10
99991 99990 11
99990 99989 12
99989 99988 13
99988 99987 14
99987 99986 15
99986 99985 16
99985 99984 17
99984 99983 18
99983 99982 19
99982 99981 20
99981 ...

result:

ok 

Test #35:

score: 0
Accepted
time: 78ms
memory: 21384kb

input:

100001
1 57767
1 15315
1 981
1 11880
1 76313
1 4577
1 88023
1 90844
1 11001
1 12900
1 46482
1 31039
1 2284
1 4038
1 2076
1 45362
1 84976
1 81694
1 63471
1 80716
1 60758
1 19471
1 11965
1 23998
1 93508
1 14996
1 1916
1 65940
1 63799
1 32745
1 8462
1 87458
1 70921
1 61066
1 8987
1 78835
1 88490
1 1165...

output:

91472 29061 1
96221 91472 2
91472 46511 3
91472 4103 4
91472 43279 5
91472 91413 6
91472 75271 7
91472 34532 8
91472 45315 9
91472 14236 10
91472 88945 11
99284 91472 12
91472 31956 13
91472 63166 14
95275 91472 15
91472 64147 16
91472 7511 17
91472 89928 18
91472 43861 19
91472 88510 20
91472 55381...

result:

ok 

Test #36:

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

input:

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

output:

impossible

result:

ok 

Test #37:

score: 0
Accepted
time: 62ms
memory: 25460kb

input:

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

output:

2 1 1000000000

result:

ok