QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#433338#7750. Revenge on My Bossucup-team3215AC ✓2053ms17892kbC++233.0kb2024-06-08 10:27:262024-06-08 10:27:26

Judging History

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

  • [2024-06-08 10:27:26]
  • 评测
  • 测评结果:AC
  • 用时:2053ms
  • 内存:17892kb
  • [2024-06-08 10:27:26]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pl = pair<ll, ll>;

void solve() {
    ll n;
    cin >> n;
    ll sum = 0;
    vector<array<ll, 3>> a(n);
    for (auto &v: a) {
        for (auto &i: v) {
            cin >> i;
        }
        sum += v[0];
    }
    auto eval = [&](const vector<ll> &p) {
        ll res = 0;
        ll sa = 0, sb = 0;
        for (auto &v: a)sa += v[0];
        for (auto i: views::reverse(p)) {
            sb += a[i][1];
            res = max(res, (sa + sb) * a[i][2]);
            sa -= a[i][0];
        }
        return res;
    };
    ll l = 0, r = 1e18 + 123;
    vector<ll> ans;
    while (r - l > 1) {
        ll m = (r + l) / 2;
        priority_queue<array<ll, 3>, vector<array<ll, 3>>, greater<>> invalid, valid;
        ll cur = 0;
        vector<ll> z;
        for (int i = 0; i < n; ++i) {
            auto &v = a[i];
            ll val = m / v[2] - sum - v[0];
            invalid.push({v[1] - v[0] - val, v[1] - v[0], i});
        }
        while (invalid.size() + valid.size()) {
            while (invalid.size() && invalid.top()[0] + cur <= 0) {
                auto it = invalid.top();
                invalid.pop();
                valid.push({it[1], it[0], it[2]});
            }
            if (valid.empty())break;
            auto it = valid.top();
            if (it[1] + cur > 0) {
                invalid.push({});
                break;
            }
            if (it[0] > 0) {
                break;
            }
            valid.pop();
            cur += it[0];
            z.push_back(it[2]);
        }
        if (invalid.size()) {
            l = m;
            continue;
        }
        vector<ll> o;
        {
            priority_queue<array<ll, 3>, vector<array<ll, 3>>, greater<>> i, v;
            vector<array<ll, 3>> zxc;
            while (valid.size())zxc.push_back(valid.top()), valid.pop();
            for (auto &[x, y, z]: zxc) {
                cur += x;
                i.push({y - x, x, z});
            }
            while (i.size() + v.size()) {
                while (i.size() && i.top()[0] + cur <= 0) {
                    auto it = i.top();
                    i.pop();
                    v.push({it[1], it[0], it[2]});
                }
                if (v.empty())break;
                auto it = v.top();
                if (it[1] + cur > 0) {
                    break;
                }
                v.pop();
                cur -= it[0];
                o.push_back(it[2]);
            }
            if (i.size() + v.size()) {
                l = m;
                continue;
            }
        }
        r = m;
        reverse(o.begin(), o.end());
        copy(o.begin(), o.end(), back_inserter(z));
        ans = z;
    }
//    cout << r << "\n";
    reverse(ans.begin(),ans.end());
    for (auto x: ans) {
        cout << x + 1 << " ";
    }
    cout << "\n";
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
    ll t;
    cin >> t;
    while (t--)solve();
}

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

详细

Test #1:

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

input:

2
4
1 1 4
5 1 5
1 9 1
9 8 1
9
3 1 4
1 5 9
2 6 5
3 5 8
9 7 9
3 2 3
8 4 6
2 6 8
3 2 7

output:

3 1 2 4 
3 4 8 2 5 9 6 1 7 

result:

ok correct

Test #2:

score: 0
Accepted
time: 1791ms
memory: 17592kb

input:

1
100000
581297 102863 1
742857 42686 1
676710 233271 1
443055 491162 1
442056 28240 1
769277 331752 1
8608 369730 1
495112 525554 1
787449 938154 1
441186 850694 1
84267 925450 1
740811 32385 1
834021 37680 1
257878 564126 1
90618 914340 1
239641 463103 1
40687 343062 1
587737 458554 1
103684 48666...

output:

70717 17982 30921 74378 77895 63986 92644 74098 72881 62031 28959 40485 89523 13855 56291 86508 94500 16970 57065 34002 22163 37156 35138 82720 29786 8015 78892 57200 41769 26467 17951 93580 32063 341 71055 36726 11306 1117 94161 51854 24764 3264 93835 911 10790 6908 3279 70716 23032 26242 36012 517...

result:

ok correct

Test #3:

score: 0
Accepted
time: 1421ms
memory: 17748kb

input:

1
99999
30245 831673 1
495617 185056 1
53028 422589 1
503558 778900 1
636981 480008 1
966864 78785 1
644954 303138 1
153080 225499 1
876411 832264 1
758904 549009 1
945000 441995 1
83780 789901 1
883282 832556 1
300776 548075 1
806599 108342 1
354979 831549 1
152110 819163 1
613891 812479 1
856259 6...

output:

12790 8995 82898 14912 72974 35724 46520 25348 46168 27296 36732 68451 23096 38702 71559 19097 34231 8968 1955 27333 37349 31989 51738 55816 53016 66070 71619 44100 75445 54440 37289 94617 62691 52491 52264 18600 1752 73434 23203 93341 6492 26926 57916 92074 10828 76163 29194 6472 54865 78988 36985 ...

result:

ok correct

Test #4:

score: 0
Accepted
time: 1932ms
memory: 17892kb

input:

1
100000
361850 684411 2
188930 167748 2
676274 449963 1
970095 784305 1
412379 854673 1
208323 612179 1
296548 633970 1
560983 633064 2
848966 248363 2
741057 340814 1
393854 435721 2
302707 834494 1
229770 235051 2
875992 747523 2
314215 448795 1
531181 809914 2
786505 95721 1
86557 773136 1
44527...

output:

63075 43512 85570 97557 92824 16488 92399 23178 73092 26476 88310 46597 88499 82211 9761 65487 6367 4286 91900 23803 86889 28708 86646 60037 59066 74495 44394 78884 17276 5416 11129 76489 1760 35519 18022 45752 25472 49520 82308 79688 48786 98697 23555 22535 94364 18713 79671 5494 90757 39984 26567 ...

result:

ok correct

Test #5:

score: 0
Accepted
time: 1893ms
memory: 17592kb

input:

1
99999
810798 413222 2
974394 310117 1
987184 606577 2
30598 6635 1
607304 306441 1
438614 583404 1
932894 375890 1
994760 333009 2
937928 950984 2
58774 6426 1
287291 728073 1
421484 592009 1
470520 62631 1
918891 764176 2
997492 642796 1
679223 178361 2
865224 571822 2
112711 192469 1
165146 9387...

output:

3283 26937 5997 68300 88387 56303 46260 14710 35230 16318 52123 28062 48240 1284 45196 48035 62358 66720 90003 38212 89023 12095 89524 81438 58757 24501 76957 33893 65549 70870 84363 25787 56371 85539 63753 75417 13424 4733 2472 42151 96285 83673 61227 10438 27632 92856 3590 26134 55252 56060 22219 ...

result:

ok correct

Test #6:

score: 0
Accepted
time: 1902ms
memory: 17624kb

input:

1
100000
142404 976360 1
924602 517001 3
610429 601247 2
529839 44745 3
606894 456914 2
488586 84093 1
360297 674019 1
435366 740573 3
943187 591275 3
8223 87831 2
703441 689095 1
673115 893499 3
817008 689318 2
237211 187815 1
472404 15953 2
822721 932534 2
275427 591484 3
393890 928933 1
11058 141...

output:

18758 61183 85616 44402 15638 57854 46413 71568 5777 6520 4574 94684 2420 85450 70235 70904 10379 98759 2863 72244 84611 58001 96203 42940 44624 72254 2189 62610 66726 25719 35529 45201 46973 41282 89947 1061 14155 58250 33539 93267 50798 53595 55773 17631 63140 38618 68799 94960 70895 57178 90936 3...

result:

ok correct

Test #7:

score: 0
Accepted
time: 1931ms
memory: 17656kb

input:

1
99999
815544 929362 2
644659 659371 3
954043 790565 3
398854 42883 3
577627 875978 2
718877 831126 1
996643 640131 2
869143 249030 3
32149 261192 1
325941 753442 3
372686 238344 2
48789 426822 2
57757 260002 1
280109 237173 3
931489 242658 2
970763 300980 2
578337 100288 1
611532 282858 3
506737 2...

output:

88611 41608 79302 67856 33740 2491 77729 35981 56917 9350 86381 27203 637 95553 78083 43929 15311 61193 28293 21659 39288 92376 64839 70915 80710 96095 33473 65681 79804 58506 22142 27589 74992 48800 95109 33696 4547 95363 78798 83475 26212 55574 30941 55126 14138 17940 82954 54061 39028 62780 95544...

result:

ok correct

Test #8:

score: 0
Accepted
time: 1883ms
memory: 17592kb

input:

1
100000
179854 525204 1
403379 866255 3
544585 817939 4
832686 337889 3
577217 283347 1
960336 331815 3
424045 970964 1
309749 591186 4
37408 677291 2
308093 545247 1
45732 199365 1
267715 728311 2
404245 919393 4
855325 436620 1
406400 774600 3
146965 279345 3
955837 376846 3
860006 276218 2
28724...

output:

10140 2079 92043 95331 58940 74502 68070 57137 5628 9445 13687 4116 82455 7000 502 10364 66071 1354 92133 76741 38198 29180 73250 40973 22308 45094 51964 28645 42994 99405 55859 40498 30096 41159 20114 52516 24634 59770 75755 15141 41356 99483 62995 53888 99490 3988 33118 20270 78261 81342 81134 233...

result:

ok correct

Test #9:

score: 0
Accepted
time: 1748ms
memory: 17804kb

input:

1
99999
628802 478207 4
156140 784432 3
920902 198745 3
925893 336026 4
772142 702412 2
190627 335745 3
93095 937076 4
710822 356539 2
126370 604104 4
625811 243562 3
714977 524422 2
386493 485827 2
677699 522781 4
898224 453274 1
89677 777113 3
262303 647792 3
291451 852947 2
886160 662847 1
848327...

output:

47184 41157 65379 49192 87605 1498 52857 41423 99008 61252 73936 6453 30677 35372 57330 71966 60867 34089 89911 60500 34814 34510 12930 66324 70969 52418 86781 89520 80648 34378 91234 44982 10903 10630 18636 72998 16411 89430 12452 49043 25628 48440 97084 66440 61882 1173 17905 63714 72039 49369 971...

result:

ok correct

Test #10:

score: 0
Accepted
time: 1676ms
memory: 17552kb

input:

1
100000
993111 41344 2
849452 991316 3
287252 969223 4
392430 565624 3
547540 852885 3
240598 836434 5
520498 11013 2
151428 698695 1
98926 987499 3
607963 259559 2
131127 518148 5
638124 530420 3
991483 116764 5
440736 876913 1
564589 309054 1
438505 593453 5
701654 872609 4
391530 399311 5
628832...

output:

56743 49472 49605 20421 96523 23202 35056 69361 51887 73420 73709 71687 87966 68065 41280 13226 82983 1365 40267 76494 32874 26302 62345 67530 21589 370 45019 78571 10751 46888 66687 11247 31476 51724 96231 67469 69493 36851 73890 63237 99210 85631 1275 78218 39431 1586 80081 32719 28393 13960 8788 ...

result:

ok correct

Test #11:

score: 0
Accepted
time: 1951ms
memory: 17636kb

input:

1
99999
633547 770155 1
634916 133686 5
855058 382733 4
485637 596466 2
742466 271949 3
470889 583467 1
156844 977125 2
585205 464048 5
187887 690121 3
892977 925171 2
57268 34693 4
981093 255232 2
232232 977047 5
516338 893566 4
247866 311567 3
586547 994603 5
4565 348710 5
417684 977428 3
124510 7...

output:

31330 88611 45879 4344 51414 29394 70327 57298 96965 24415 67221 99424 66729 97656 24618 31768 19344 5745 20929 97701 47119 57544 38883 86246 48045 59687 33142 34040 61731 21801 81473 35820 14679 43377 6292 62337 62928 58732 14019 90287 55784 19662 16793 38931 73106 14667 18488 52127 50047 20524 329...

result:

ok correct

Test #12:

score: 0
Accepted
time: 1989ms
memory: 17568kb

input:

1
100000
997857 590189 5
552421 307866 1
221408 153211 4
952174 826064 4
742055 646614 4
712348 116860 2
808438 307957 5
250004 806205 1
193147 297708 2
875130 941168 5
473418 995714 5
975828 556721 3
578721 379543 1
834658 317206 4
722778 876212 3
730045 972968 6
414768 657972 1
633455 746596 6
970...

output:

82707 44421 79357 47005 10318 31274 14336 8766 82315 34805 61639 86838 19731 44189 27168 19944 5020 68920 44624 98370 84383 546 50931 71647 41497 81482 78683 97326 11092 42443 24877 47509 47657 25 15825 78270 83050 98146 44800 80851 43024 60476 92433 23581 51074 78132 37871 79227 55101 59114 25748 4...

result:

ok correct

Test #13:

score: 0
Accepted
time: 1796ms
memory: 17612kb

input:

1
99999
414101 318999 4
305181 450235 4
789213 599425 5
12677 889610 6
936981 98382 2
942639 831190 3
444784 241365 4
683780 538854 3
314812 329 6
192848 447995 3
142664 320771 6
384205 90044 2
595278 174418 6
877557 109667 2
181863 102918 3
910791 341415 2
526191 134073 2
659609 133225 3
690293 561...

output:

10560 88857 13508 54916 59783 55487 47921 92513 46595 6009 82779 13438 82035 79141 99242 5562 35875 64124 7205 58929 49836 45488 89697 33738 98260 47428 45271 9319 31781 76796 2188 66620 48510 3507 9757 646 25764 31882 50355 46789 655 66157 1791 60347 82552 31425 62142 23381 4457 35103 88728 16070 6...

result:

ok correct

Test #14:

score: 0
Accepted
time: 1716ms
memory: 17624kb

input:

1
100000
778411 171737 3
31198 657119 3
155563 369903 1
511917 119207 6
679674 248855 4
992610 588775 5
872187 572198 6
91683 913714 4
254664 416428 3
175000 463992 3
815710 281793 4
603132 358830 2
165958 576913 2
420069 533307 7
656775 410667 2
278481 287076 5
160586 153734 2
164979 126586 2
27930...

output:

17286 87861 8125 35745 71355 85902 67689 37360 38799 60303 95565 17904 66522 96851 35035 16903 18822 75780 49334 87051 83432 41654 16075 98248 22325 37765 45532 93155 88480 39762 19508 23338 24449 3568 97327 84711 12391 67726 76480 97722 40423 8461 51199 66900 72993 3921 1181 81827 56413 15967 93023...

result:

ok correct

Test #15:

score: 0
Accepted
time: 2002ms
memory: 17564kb

input:

1
99999
451551 900548 5
783958 575297 1
756073 750709 5
605124 150049 5
907304 667919 2
190198 335808 4
508533 538310 7
525460 422171 6
409034 310537 1
268526 129603 1
484955 798337 5
946101 116345 4
215220 404493 1
495671 549960 7
340051 637372 6
169627 688226 2
206600 629835 3
191133 480511 4
3188...

output:

54575 26118 74194 24671 76709 96324 15017 65562 57058 6952 19824 21465 6194 51584 36673 3147 62370 12466 12647 55914 25107 96273 81038 12721 84451 47927 15112 87684 61199 36442 29974 73629 27745 21226 79438 17785 89519 34016 49272 61302 25613 80595 37955 57420 69379 17847 97125 81451 26086 91560 603...

result:

ok correct

Test #16:

score: 0
Accepted
time: 2053ms
memory: 17576kb

input:

1
100000
783156 687878 1
477270 782181 2
122423 521187 1
814765 379647 8
906893 42584 3
464361 836497 8
935935 677655 6
966066 829735 7
348885 726636 6
474870 178304 5
901105 792063 5
940836 193643 7
785900 806988 3
38183 973599 4
814963 945121 3
570021 666591 6
840996 939097 7
406903 216975 2
62090...

output:

79676 7754 59983 88410 81261 57670 88914 95097 15826 30645 74607 59527 86643 89629 48361 83216 48739 94032 38310 44494 41435 1418 14464 64251 84896 81848 40604 25019 31733 68544 21066 31440 60919 32192 41949 60076 29161 58157 24841 73175 15509 14051 88190 96911 2557 60157 49398 9040 91037 44011 9539...

result:

ok correct

Test #17:

score: 0
Accepted
time: 2016ms
memory: 17796kb

input:

1
99999
45362 965532 6
708808 306508 2
624384 151389 1
467716 670928 1
39438 96594 5
942210 88149 7
892926 875304 8
241522 637190 1
564772 772170 8
835563 334036 7
104129 627390 5
911109 785971 7
389695 864643 9
475004 239058 3
432237 738985 3
818115 349146 8
665532 910961 8
964582 950889 9
682361 7...

output:

69080 72247 68451 87189 49283 10013 59567 74871 41854 22043 637 83683 18715 307 8037 95284 8550 86733 51914 57844 14963 23738 27295 38088 95720 1056 19387 90201 31596 56167 15609 33129 72465 19455 12861 83892 54636 20712 49640 30935 5968 45780 36714 38909 46486 88081 80612 69538 36565 86096 4987 499...

result:

ok correct

Test #18:

score: 0
Accepted
time: 1820ms
memory: 17544kb

input:

1
100000
545343 214678 2
896330 34297 10
225650 145117 5
3539 141992 10
866014 337066 4
787360 33077 10
990193 565400 7
746446 687990 6
657093 370479 9
221001 777823 3
818490 795673 2
891597 771810 3
322069 291555 3
680477 429062 4
131032 471991 3
498884 709254 9
4962 615960 7
537100 173421 1
166345...

output:

66213 30020 71184 26336 93319 16825 69579 90927 35175 88353 76840 82572 81522 85577 5172 49095 16775 73894 88626 18480 82569 18940 63703 81533 26048 9452 45885 36435 85893 47585 16095 54136 33663 44412 19360 35936 11437 97570 92097 12539 70473 78994 81838 35012 76821 2557 3963 93635 28678 59532 7606...

result:

ok correct

Test #19:

score: 0
Accepted
time: 2011ms
memory: 17584kb

input:

1
99999
336110 764075 4
762927 765956 4
275286 70789 5
459972 469529 7
870966 316414 7
498229 41636 11
830500 307315 6
854475 488251 5
759873 905341 5
993842 970385 9
217019 809676 12
207189 933113 4
625602 520131 7
736635 340574 11
921162 795091 6
552353 769663 10
406594 84507 8
465432 768495 3
892...

output:

91079 54539 11759 13393 43844 7248 27810 36733 94977 49223 67537 56342 51208 55532 53689 48022 90058 4490 47874 73259 8211 55570 69214 18583 18981 322 6571 68798 39651 34417 317 42565 61454 79220 83589 11890 79380 93681 51029 52639 82080 96166 62670 91006 1541 50732 38650 70936 85072 64769 83854 612...

result:

ok correct

Test #20:

score: 0
Accepted
time: 1938ms
memory: 17712kb

input:

1
100000
108561 606864 17
350323 824178 19
354491 276661 2
386504 972995 8
126712 330871 13
27512 558033 16
821693 489290 10
531173 946706 11
851074 696984 13
215023 489278 3
550601 849390 9
18144 714207 18
493423 166694 1
682070 122973 15
480819 38485 4
803701 169413 20
175493 785397 12
948045 5586...

output:

15247 35768 39103 75743 90686 29715 3384 24024 60091 72778 11385 80666 3867 77249 34551 6681 78918 14153 48529 34467 63101 8897 66196 18830 89147 57036 68091 68926 75071 81677 74269 60267 15685 99664 74802 27441 28015 35770 76617 60458 54373 26454 9906 4462 30248 63670 50044 15110 48070 98932 12077 ...

result:

ok correct

Test #21:

score: 0
Accepted
time: 1745ms
memory: 17756kb

input:

1
99999
270178 61120 9
118244 697562 5
796784 638127 10
716782 572441 25
868171 877138 2
451141 273737 29
917860 184163 26
669039 916520 30
900920 422991 7
772136 494308 18
675065 814143 30
968370 228164 17
447803 120035 26
195744 975315 19
310881 998911 19
512798 212819 4
789254 622264 22
984709 59...

output:

84170 75119 93847 72680 12156 5973 32129 50224 63698 95295 48989 92616 56035 23168 13838 15638 3726 172 93287 11826 46445 80396 66880 18119 98933 18428 80361 36851 39863 2382 52103 93485 14360 95703 5140 46772 61891 64421 19023 48240 37460 52275 40295 58840 59288 11302 39223 1595 80073 33451 53071 2...

result:

ok correct

Test #22:

score: 0
Accepted
time: 2000ms
memory: 17632kb

input:

1
100000
87815 816125 15
712301 586652 26
997911 895483 38
726884 50324 43
427717 312286 28
196351 258982 19
474976 452448 13
371565 914341 28
848695 643798 25
229795 39321 27
129910 753647 6
206296 219095 38
680062 142384 26
752256 980514 31
628293 803374 32
592071 806785 7
70061 583309 35
732498 3...

output:

49980 26767 38985 90624 38108 63181 11077 24079 18349 28377 89204 46518 65805 76773 60092 95506 59101 72547 34653 57717 64600 51241 35841 72113 28449 78597 90708 12216 52171 34498 43678 62242 55904 11909 66621 95876 24501 62702 26907 28867 60080 86782 36555 48362 13305 97798 6439 46921 68144 39336 4...

result:

ok correct

Test #23:

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

input:

1
99999
969047 371 41
853468 252554 79
784554 756858 19
945912 189669 56
28679 367615 21
745635 438170 93
394681 487499 76
986024 222074 12
796761 902579 3
934082 772826 5
848868 475664 57
928859 487080 17
447261 415165 48
324804 77833 94
513254 520849 43
811124 531448 22
414298 235550 92
662853 204...

output:

18410 37562 76379 53983 63893 84005 35088 93379 48150 51273 62227 90013 28977 35159 27971 85291 25921 17635 13440 7367 78276 82107 55731 49021 23292 77554 54112 17170 7113 87827 5859 77208 79624 17599 74936 56099 61419 84130 35262 84761 8061 99847 59575 90828 50509 57651 1554 24752 30777 24192 15478...

result:

ok correct

Test #24:

score: 0
Accepted
time: 2032ms
memory: 17748kb

input:

1
100000
14578 331976 83
739173 945866 58
769064 123208 197
657914 688910 162
63712 334500 95
112850 488141 182
673605 139094 109
8038 662680 177
139883 875134 102
240255 754978 10
139120 891814 83
967220 706007 107
811284 728949 43
749285 653050 130
42454 995761 196
897079 899138 87
585743 869946 6...

output:

48898 84701 24076 69502 1100 68678 72996 35128 10758 31147 44016 86316 67405 79820 19005 12386 65080 93628 68318 930 46572 18378 4437 93552 4710 48057 24995 14252 43963 4035 85008 34541 35732 18940 53861 83955 39386 360 74814 23567 81471 29398 93779 41459 98011 79620 92213 50799 66662 94643 57335 64...

result:

ok correct

Test #25:

score: 0
Accepted
time: 1711ms
memory: 17612kb

input:

1
99999
776558 379481 222
389786 326445 297
33988 301992 167
922081 171748 27
44539 631883 366
435819 942194 271
728896 223581 455
306860 878391 458
944588 214055 460
459371 939603 266
655301 555228 355
491970 417096 153
318104 764115 348
829143 260691 86
14484 737924 368
508188 763016 368
738889 88...

output:

81546 19191 6236 59754 93708 30190 93367 91877 43727 86267 82108 15238 29145 9555 45970 1648 34213 60630 16890 86935 6072 60504 99348 95651 23789 46905 45480 22942 54091 6387 91688 60170 18181 19445 97234 55996 12610 18370 71018 62053 9057 37242 80867 97134 28183 69353 8132 62030 61735 43163 28294 6...

result:

ok correct

Test #26:

score: 0
Accepted
time: 1783ms
memory: 17632kb

input:

1
100000
953776 515469 53
574495 620563 408
331343 705288 552
307179 689650 745
108389 820839 791
831194 34474 881
928795 832739 27
162288 848143 103
438197 683261 522
872355 234923 123
275412 349154 731
403641 327600 231
642668 821247 651
639908 457535 877
184578 621090 792
483486 866841 827
382761...

output:

72979 35432 38893 27481 95861 35243 33135 80434 35764 74247 24096 4519 54194 89268 73618 64503 89075 22169 77362 62366 64629 13424 14411 20117 10130 23133 27784 92500 20702 74774 93043 2300 44382 70908 92580 13079 34305 22861 2020 76315 52187 3509 34189 39890 29507 62775 44212 32072 39246 530 4114 3...

result:

ok correct

Test #27:

score: 0
Accepted
time: 2047ms
memory: 17664kb

input:

1
99999
128495 399445 763
873699 750462 2051
771645 791001 3841
668391 425718 3815
274257 54791 3769
572299 402750 3749
622972 357997 1273
354814 50592 1657
409819 763434 3342
941450 774102 2301
705607 604543 3333
441889 400571 2267
563457 738075 3090
751849 8690 1656
524888 757409 1699
294794 33160...

output:

42264 3515 80000 85134 54847 56318 83836 35432 29070 86169 3798 34456 12143 7738 31798 87350 29857 51770 97039 82173 41890 60272 7407 84522 59716 87038 65189 81380 64592 62346 3912 11466 98670 72247 49085 59378 41744 85277 80905 65152 90593 71843 64848 8281 44392 98063 41067 44271 85557 26757 422 32...

result:

ok correct

Test #28:

score: 0
Accepted
time: 2050ms
memory: 17788kb

input:

1
100000
722958 355226 2094
266625 467230 8712
979360 944520 2487
295170 735423 2727
722419 313725 3199
789942 961946 9194
700692 559861 7780
649116 795879 2218
690710 741191 3253
493019 510759 8703
230105 693648 3581
776356 568494 6123
384478 553056 8000
262437 617457 2646
944585 4132 9669
239024 3...

output:

10131 24978 30780 53069 31261 73020 68156 36536 59254 64221 97660 33865 15649 30858 73977 12726 57342 69529 79415 77489 11637 90087 10216 76520 56508 86980 39157 93644 18733 42636 67220 9893 22178 50607 69955 26758 13342 33427 70819 23796 44247 54308 19237 20439 49694 66939 18783 68933 60893 83946 8...

result:

ok correct

Test #29:

score: 0
Accepted
time: 1751ms
memory: 17632kb

input:

1
99999
846662 746684 27049
416087 114018 39556
827768 480922 19619
538880 640896 35309
974134 999365 37801
462745 682933 806
606482 571441 8720
401083 408557 32312
797890 970757 39099
378069 473292 33198
452952 185965 42390
524236 671077 29109
746622 849987 48916
692368 638905 26915
476085 504542 1...

output:

20409 55359 67401 50964 44531 70760 65343 42512 33274 43544 69352 34435 44240 55742 4676 26934 39316 97974 95302 43944 6657 28372 82452 74982 63326 9684 10275 5895 31369 55386 47392 47942 56176 86485 19253 92106 72444 95409 98176 10169 50881 61188 16749 35987 77123 58701 56783 94680 53001 63450 1232...

result:

ok correct

Test #30:

score: 0
Accepted
time: 1713ms
memory: 17668kb

input:

1
100000
971466 923902 13036
178471 298728 9482
405999 2470 22915
603996 25994 53211
456448 30511 11349
18316 78308 17277
863127 738636 42069
857249 263985 26256
617839 464366 58305
395945 918980 28518
969530 806076 36316
806039 806940 96509
282118 141847 56048
595896 449670 41054
190736 674636 4589...

output:

32636 25572 31327 5105 73489 1520 87870 84989 48605 69601 5236 15511 13746 23195 97426 35557 10853 22737 49501 4861 1552 30987 52296 75995 45805 75638 96549 55790 75510 56239 41387 28266 86279 49297 82613 54741 93378 88371 32995 51098 90439 85556 12354 13549 43768 38598 90260 98209 26374 32283 55831...

result:

ok correct

Test #31:

score: 0
Accepted
time: 1799ms
memory: 17556kb

input:

1
99999
932826 868158 836741
757509 147472 90812
420972 457136 757627
569138 433050 395584
828836 391573 506718
940415 3167 875552
397212 243182 713853
389349 453435 165834
612841 415193 497972
43233 799293 174303
652096 485581 690886
929649 7236 344171
963593 933013 38136
677458 266199 985380
12930...

output:

59703 76481 350 22392 27198 88208 89877 54131 72348 35732 53636 90150 64374 31327 79937 91342 52216 48316 96884 85909 29377 22505 77178 62146 71913 26127 3195 27910 91004 46679 75746 52688 44167 15484 21363 87931 19499 538 14466 43079 29223 10587 21241 736 71486 59351 69468 25885 79181 176 95039 929...

result:

ok correct

Test #32:

score: 0
Accepted
time: 651ms
memory: 14076kb

input:

1
100000
1000000 1000000 1000000
1000000 1000000 1000000
1000000 1000000 1000000
1000000 1000000 1000000
1000000 1000000 1000000
1000000 1000000 1000000
1000000 1000000 1000000
1000000 1000000 1000000
1000000 1000000 1000000
1000000 1000000 1000000
1000000 1000000 1000000
1000000 1000000 1000000
100...

output:

100000 99999 99998 99997 99996 99995 99994 99993 99992 99991 99990 99989 99988 99987 99986 99985 99984 99983 99982 99981 99980 99979 99978 99977 99976 99975 99974 99973 99972 99971 99970 99969 99968 99967 99966 99965 99964 99963 99962 99961 99960 99959 99958 99957 99956 99955 99954 99953 99952 99951...

result:

ok correct

Test #33:

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

input:

1
10
2 10 1
8 10 6
4 4 9
6 7 5
5 6 4
7 10 9
7 7 7
4 9 6
4 5 7
1 1 7

output:

5 4 9 2 8 1 6 3 7 10 

result:

ok correct

Test #34:

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

input:

1
10
485566 661308 221125
602000 2 6
714165 6 3
7 596643 587186
7 985484 2
197190 2 2
7027 8 5
10 5 8
621058 1 688117
10 633379 164945

output:

1 10 5 4 9 8 7 6 2 3 

result:

ok correct

Test #35:

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

input:

1
500
229 232 88
36 27 60
158 1 343
356 247 333
440 3 271
420 78 50
181 212 302
384 444 209
284 184 393
416 482 51
242 373 331
355 470 251
382 151 262
206 32 237
483 310 124
275 93 258
212 154 247
379 62 28
456 185 159
454 82 476
168 46 144
17 312 499
10 77 276
339 173 69
330 373 17
256 448 498
223 ...

output:

1 100 62 118 368 494 459 150 396 461 489 173 33 122 445 299 7 131 496 179 202 398 25 97 29 39 41 477 303 301 147 374 205 256 68 189 8 397 279 307 415 10 64 23 433 129 296 126 378 151 484 284 27 187 353 119 286 341 231 199 436 370 467 474 105 441 210 12 422 389 358 11 290 334 345 86 236 456 313 178 2...

result:

ok correct

Test #36:

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

input:

1
500
20004 38 372
100 16 181
149374 35468 294245
126267 486 452
286 412 200
747456 213887 767656
117 847144 226
308111 342 520765
304 80 110121
49258 561097 546419
63074 509481 733960
126 775895 373701
339 365928 385
30 199 318
134197 411 103412
5333 220 336
87 489 25508
166200 987909 511327
476 35...

output:

336 95 237 319 384 138 207 151 481 300 125 146 367 361 198 238 214 399 93 304 329 426 273 91 301 356 5 105 454 270 14 375 227 71 164 241 271 358 338 445 325 412 391 226 340 316 17 180 258 478 293 229 236 155 244 26 181 337 407 86 298 182 332 201 353 235 496 276 341 471 33 499 363 309 432 365 457 124...

result:

ok correct

Test #37:

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

input:

1
1
1 1 1

output:

1 

result:

ok correct

Test #38:

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

input:

1
1
796328 1 719733

output:

1 

result:

ok correct

Test #39:

score: 0
Accepted
time: 1811ms
memory: 17632kb

input:

1
100000
61850 84411 46680
88930 67748 47416
76274 49963 99253
70095 84305 34027
12379 54673 14197
8323 12179 31657
96548 33970 69265
60983 33064 76580
48966 48363 63608
41057 40814 26167
93854 35721 27144
2707 34494 18821
29770 35051 54832
75992 47523 9044
14215 48795 25989
31181 9914 69544
86505 9...

output:

76173 78645 94636 37412 45965 62082 9618 44518 16361 63075 61352 11813 42818 90751 56762 62150 74210 13779 43270 1335 14404 9185 86653 29436 49074 17887 86690 28279 93456 66370 11134 60452 99915 90601 84390 82189 20578 89023 20030 20102 13888 40794 37727 51182 91280 61826 22698 22454 18301 21643 310...

result:

ok correct

Test #40:

score: 0
Accepted
time: 1714ms
memory: 17576kb

input:

1
100000
924602 76894 76360
529839 605505 1247
488586 3766 456914
435366 724358 674019
8223 142516 591275
673115 962254 689095
237211 66450 89318
22721 63332 15953
393890 854351 591484
17037 15993 141132
11900 8268 23752
2906 528321 54437
93877 9808 79501
959623 40054 54992
86687 65830 886221
160821...

output:

58172 93386 94458 98315 20324 86395 84324 9706 43955 34199 28040 2787 42932 32500 38419 57217 62062 25452 68418 50341 63518 26822 4083 49688 1665 50149 5249 76132 45890 83531 97779 92938 11119 46727 51911 72920 37599 92848 2169 24504 35274 26227 86175 26882 23458 11256 10065 30499 19564 38518 88055 ...

result:

ok correct

Test #41:

score: 0
Accepted
time: 1310ms
memory: 14148kb

input:

2
69821
88401 742421 1
794466 913634 1
103831 780090 1
194366 83442 1
891069 901851 1
14782 827286 1
629158 268122 1
511572 261569 1
64650 726005 1
435161 580063 1
108579 365076 1
257108 490883 1
723162 813583 1
816841 933459 1
333041 428483 1
211846 962418 1
723314 157335 1
837290 54766 1
138584 58...

output:

12731 37757 10632 25100 44317 15158 24990 56560 3385 54847 50345 7714 41297 11249 57822 58957 20579 48424 65894 30202 41778 18077 41589 54876 3094 66223 43850 43936 12863 44952 28089 65731 10714 63092 53909 65259 25086 13082 18449 46584 34093 46267 32495 31424 13171 51562 66032 46408 7302 39555 2353...

result:

ok correct

Test #42:

score: 0
Accepted
time: 584ms
memory: 4016kb

input:

300
253
830133 947891 1
363214 158400 1
678623 525243 1
557424 435477 1
140409 99787 1
957753 183966 1
626409 249098 1
710920 607523 1
15679 17828 1
876419 80539 1
167749 400048 1
269258 222458 1
150536 140001 1
666204 606142 1
46951 206706 1
655815 806710 1
258588 306955 1
735893 932947 1
841224 14...

output:

180 9 124 35 117 214 120 179 174 98 60 166 17 64 195 230 201 209 36 104 204 125 140 1 43 144 57 113 22 16 226 103 156 123 165 84 15 97 248 21 25 159 18 66 245 11 252 205 73 220 247 107 187 136 153 243 200 253 211 235 56 115 244 126 105 160 155 234 59 38 85 240 48 67 27 164 32 168 29 119 37 227 249 1...

result:

ok correct

Test #43:

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

input:

10000
1
425023 723812 1
13
836095 863384 1
233225 596397 1
566137 236643 1
268085 280508 1
223291 393445 1
809612 382630 1
151088 862073 1
173393 927632 1
17049 195961 1
677649 745628 1
36991 667660 1
298669 836826 1
362975 372403 1
1
963621 249133 1
6
3536 279568 1
587752 487419 1
83384 748663 1
58...

output:

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

result:

ok correct

Test #44:

score: 0
Accepted
time: 565ms
memory: 9332kb

input:

2
4037
464131 318220 1
90991 541050 2
766311 591558 1
742307 17787 1
781261 488145 1
357957 347184 1
633182 301261 1
94682 843291 1
631637 529027 2
82521 704473 1
437456 276755 2
778263 51432 1
786584 977440 1
833333 648570 1
552303 601466 2
938184 44857 1
794073 277387 1
994953 290395 1
935853 1864...

output:

524 584 2738 903 738 436 2037 3133 2259 636 529 1772 3607 619 2432 3442 2196 2481 270 1226 3228 2173 215 2691 981 1752 1138 1261 2520 2839 320 456 251 3116 1035 888 195 479 3573 2383 1733 2589 1895 668 571 1738 460 1396 3982 3435 2832 925 419 1734 1311 563 2212 2347 2398 3774 1950 2778 2473 3266 189...

result:

ok correct

Test #45:

score: 0
Accepted
time: 649ms
memory: 3708kb

input:

300
134
36059 286818 2
455971 795720 2
74275 63495 1
75077 509010 2
503679 169175 2
11185 421244 1
437281 322883 2
869878 384461 1
191807 672570 1
288040 312855 1
660008 723414 2
221648 416391 2
624391 145096 1
411858 695660 1
578102 665090 2
890142 668549 1
608518 448483 2
113307 706064 1
283662 63...

output:

89 24 98 10 77 67 23 112 45 123 99 32 29 117 14 40 92 19 71 87 110 90 50 6 43 28 113 109 36 9 104 91 18 127 25 97 133 62 22 63 102 128 55 70 107 52 11 15 64 31 12 108 122 1 33 61 68 101 2 72 78 129 4 54 80 41 79 132 84 94 38 48 134 105 46 7 74 17 103 111 114 130 76 5 51 82 88 37 60 131 39 26 121 56 ...

result:

ok correct

Test #46:

score: 0
Accepted
time: 481ms
memory: 3596kb

input:

10000
2
525139 532331 2
923628 228718 1
6
234983 515915 1
705263 115904 2
902643 575572 1
90796 310572 1
191007 876742 1
926631 224132 2
1
363621 733700 1
16
617390 281024 2
354701 28586 2
902129 562488 1
711461 107434 1
714910 223331 2
835971 497838 1
118657 220815 2
375999 800233 1
180250 455648 2...

output:

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

result:

ok correct

Test #47:

score: 0
Accepted
time: 19ms
memory: 3728kb

input:

2
1389
643295 305353 1
17366 456325 2
596129 942726 1
830936 621567 2
604681 76325 1
774761 275083 3
176002 127294 2
580914 456741 3
634013 437706 1
24737 134880 1
556648 720413 2
801133 640387 2
9231 991784 3
966796 684261 1
847283 768303 2
804657 879431 2
288649 139591 3
511819 701938 1
27061 5639...

output:

1024 757 513 689 374 418 620 1187 461 783 329 1199 1081 692 1318 948 1012 55 718 166 401 1284 92 828 93 702 465 743 1279 585 651 671 727 318 617 1384 1135 1316 780 56 156 886 1201 33 500 605 1256 819 117 432 1019 1115 931 30 1250 941 98 1310 752 1312 1160 180 893 315 185 503 126 16 346 253 387 790 3...

result:

ok correct

Test #48:

score: 0
Accepted
time: 652ms
memory: 3796kb

input:

300
251
789119 100187 2
697580 571877 2
686584 10582 2
418190 372990 2
788026 231797 3
985515 398910 3
237323 766683 2
364345 244638 2
629965 746778 3
442153 340088 3
998666 429796 1
755218 985359 3
840002 539125 1
373406 54563 3
638707 859838 2
656500 817395 3
899880 742356 1
90021 71315 1
883077 9...

output:

163 138 207 47 234 97 70 157 148 206 167 124 82 121 243 210 81 232 102 133 228 114 191 56 57 188 166 15 244 227 217 28 131 51 224 218 128 61 26 125 63 192 196 90 153 115 164 208 111 193 182 84 176 152 248 37 88 40 25 238 60 178 62 200 194 205 180 7 139 122 23 169 158 225 24 67 72 104 183 174 215 202...

result:

ok correct

Test #49:

score: 0
Accepted
time: 508ms
memory: 3592kb

input:

10000
9
340849 332736 2
337156 473580 3
725034 883073 1
219356 12503 2
936044 549719 3
227698 971858 2
370855 568407 1
618895 291761 2
507065 78488 2
8
333383 660664 1
344247 932637 3
200420 429670 2
536827 573382 1
106963 127237 2
713838 866936 2
162062 279088 1
145752 929994 1
4
905737 522662 1
53...

output:

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

result:

ok correct

Test #50:

score: 0
Accepted
time: 1016ms
memory: 11100kb

input:

2
2795
297292 539767 8
734875 511215 9
667232 536489 8
634005 856493 3
580380 622144 4
581010 98539 9
919508 825607 6
524199 860110 5
802059 591467 8
885913 685100 5
565378 910253 9
490311 943067 1
567041 155343 7
328533 943487 1
154277 487096 1
812892 214739 10
113962 103658 5
687184 187384 6
83481...

output:

1988 416 1864 2762 2745 2466 2522 400 1177 1585 2601 845 795 480 1365 729 1708 1472 1349 2643 96 1406 869 2076 1697 2742 1494 745 2775 1084 556 1665 875 424 2664 2504 1097 116 2143 854 975 2368 202 1857 38 2735 2120 972 1947 2190 1707 131 137 143 2432 1228 561 1506 664 2508 1600 2112 773 5 2025 2746...

result:

ok correct

Test #51:

score: 0
Accepted
time: 677ms
memory: 3820kb

input:

300
313
181024 742572 1
847307 106677 9
375980 457310 10
944809 442603 4
570686 894299 8
124371 282741 6
44756 196447 1
312495 303886 8
855637 365548 2
972108 981965 9
657516 19589 9
184806 920191 8
29602 361256 6
752410 616901 2
758651 50575 9
571691 387695 5
601171 137962 8
707125 753434 5
644216 ...

output:

21 74 289 255 203 28 236 167 18 43 311 68 195 228 213 259 49 173 150 171 269 263 126 232 170 181 56 117 96 97 231 172 65 7 189 6 308 79 136 24 276 243 116 190 295 44 144 120 51 244 103 111 211 72 220 247 257 13 252 109 88 217 62 169 54 221 226 179 227 205 164 250 156 107 89 271 206 90 57 313 246 130...

result:

ok correct

Test #52:

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

input:

10000
17
780658 578371 3
47635 686616 8
318753 263312 2
655616 417338 1
224671 828602 9
230974 643576 4
874831 202616 2
177657 47352 1
619169 180834 6
337414 98608 8
14938 561758 2
190162 790130 8
422120 130445 3
907851 740409 5
310886 389878 7
659021 276403 7
973677 834994 7
11
229775 712783 3
6087...

output:

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

result:

ok correct

Test #53:

score: 0
Accepted
time: 1286ms
memory: 10284kb

input:

2
48688
685632 618517 40
946415 334447 43
752761 979212 40
433885 69891 33
569670 946047 93
555989 124478 93
274327 869785 90
485360 45389 42
23642 844669 87
140871 587747 87
869963 693679 53
676186 65537 42
881980 192065 40
873410 311493 61
534245 627841 18
244185 178870 82
499887 451233 95
57767 1...

output:

24823 48367 46302 32632 43961 133 47804 14031 45292 46201 17773 3230 38773 24925 3274 1509 32564 13006 25623 48115 2692 46057 24008 3652 567 8629 1671 35252 46386 37215 11509 44382 2988 17076 17470 30149 34997 32365 36089 7938 1146 7223 40667 35058 18837 5037 11396 25279 30465 45147 39751 44169 3230...

result:

ok correct

Test #54:

score: 0
Accepted
time: 664ms
memory: 3824kb

input:

300
420
669837 320560 61
258799 886730 73
164105 746610 57
84838 703770 100
636583 273782 59
825002 115141 78
369165 503638 51
53323 943414 79
179758 717391 39
255236 708325 60
241304 628458 67
884196 464104 76
930360 853422 67
337726 677439 64
580974 613764 10
122706 882972 69
57560 259562 36
45657...

output:

223 330 45 15 104 363 321 94 406 298 412 378 273 311 345 196 93 214 55 259 57 280 407 309 387 74 370 299 58 346 215 377 77 238 7 251 218 239 133 102 419 290 391 166 334 17 404 137 61 109 250 297 154 379 86 260 117 315 53 35 256 410 206 124 180 307 233 227 156 353 127 197 114 97 178 398 146 284 14 24...

result:

ok correct

Test #55:

score: 0
Accepted
time: 477ms
memory: 3816kb

input:

10000
23
973684 7831 94
537048 731681 14
882601 751411 72
431976 93550 32
816227 731555 4
7075 314732 17
268202 295472 66
798245 717683 68
660640 145985 83
243308 363161 59
498791 751204 31
621033 843418 6
970638 854301 50
968200 810305 100
401858 497645 91
320766 661915 35
832051 354020 26
871379 8...

output:

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

result:

ok correct

Test #56:

score: 0
Accepted
time: 560ms
memory: 3620kb

input:

20000
5
564336 480387 1
430553 699081 1
278563 238435 1
419891 873247 1
776080 588695 1
5
970707 986491 1
988325 837799 1
616860 966847 1
927749 400769 1
793152 488151 1
5
217283 631630 1
967252 903221 1
354591 389526 1
62194 938123 1
835140 509270 1
5
510932 530250 1
959618 144352 1
770415 705305 1...

output:

4 2 3 1 5 
1 3 2 5 4 
4 3 1 2 5 
1 5 3 4 2 
3 5 1 2 4 
1 5 2 3 4 
2 5 1 3 4 
2 1 3 5 4 
2 5 1 3 4 
4 5 2 3 1 
2 4 5 3 1 
2 4 3 1 5 
5 4 3 2 1 
4 3 2 1 5 
2 5 1 4 3 
2 3 1 4 5 
1 4 5 3 2 
3 2 5 1 4 
2 4 5 3 1 
5 4 2 3 1 
5 4 3 1 2 
4 2 3 5 1 
4 5 1 3 2 
2 1 5 4 3 
3 4 5 1 2 
4 3 5 2 1 
1 4 3 2 5 
1 4...

result:

ok correct

Test #57:

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

input:

10000
10
246428 90732 1
303821 684428 1
301599 422756 1
515216 177567 1
321822 555733 1
994857 742288 1
371128 250193 1
31645 742720 1
783257 82443 1
830750 747553 1
10
461123 817287 1
199478 259329 1
726303 791746 1
27694 235096 1
859908 373085 1
644286 804111 1
225287 406992 1
847610 747793 1
9096...

output:

8 3 5 2 10 7 1 6 4 9 
2 3 6 7 4 1 8 9 5 10 
1 3 7 9 8 4 2 5 6 10 
10 2 9 7 5 3 4 8 1 6 
3 4 7 6 2 8 10 1 9 5 
2 3 1 10 6 9 8 7 4 5 
8 6 1 9 7 5 2 3 10 4 
2 8 4 9 6 5 7 3 10 1 
3 4 6 1 7 8 9 2 10 5 
2 10 8 1 9 7 5 4 3 6 
4 3 5 6 10 9 8 1 2 7 
3 6 4 2 1 10 8 7 5 9 
8 3 1 4 6 5 10 7 2 9 
5 9 3 8 4 7 2 ...

result:

ok correct

Test #58:

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

input:

5000
20
875906 903989 1
75804 163205 1
605781 389616 1
315307 704607 1
769739 526056 1
425579 22550 1
294714 313941 1
345502 617103 1
208118 176664 1
349977 14719 1
437260 126874 1
66912 821226 1
259518 411687 1
969283 629018 1
677888 307082 1
334904 95651 1
668531 120105 1
807802 22421 1
989024 435...

output:

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

result:

ok correct

Test #59:

score: 0
Accepted
time: 437ms
memory: 3812kb

input:

2000
50
988531 726738 1
872842 823728 1
518328 224786 1
715577 126942 1
146194 885409 1
652337 989417 1
546559 762083 1
352481 431741 1
706893 426624 1
99143 881626 1
300261 929556 1
827997 156642 1
340250 173400 1
532034 226466 1
361138 590160 1
149862 2975 1
549878 67959 1
562298 327394 1
128887 2...

output:

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

result:

ok correct

Test #60:

score: 0
Accepted
time: 555ms
memory: 3832kb

input:

20000
5
569082 996527 2
133522 791438 2
212718 422423 2
946931 133687 2
970595 415128 1
5
475161 234214 1
276266 910552 2
458540 817460 2
21970 710977 2
60318 202464 1
5
335382 950413 1
370364 738034 1
941829 619601 2
680309 154224 2
993329 267917 1
5
835176 877061 2
672732 705523 2
301939 52590 2
3...

output:

2 3 1 4 5 
5 4 3 2 1 
2 1 3 4 5 
4 2 1 5 3 
1 3 5 4 2 
4 3 1 2 5 
2 3 4 5 1 
3 4 5 2 1 
3 5 4 2 1 
2 4 1 5 3 
1 2 5 3 4 
2 3 5 1 4 
2 1 3 5 4 
1 2 5 4 3 
2 5 3 1 4 
5 3 4 2 1 
1 2 4 5 3 
1 2 5 3 4 
2 1 5 3 4 
5 4 2 1 3 
1 3 4 2 5 
4 5 1 3 2 
5 1 4 2 3 
2 4 1 3 5 
3 5 4 1 2 
1 2 3 5 4 
2 5 3 4 1 
4 3...

result:

ok correct

Test #61:

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

input:

10000
10
26982 672280 1
782598 809490 2
235754 606744 1
42256 438007 1
292145 382166 2
466607 990010 1
434877 547137 1
873324 850229 2
844774 425355 1
130621 429161 1
10
579222 103366 2
826782 61438 2
313541 21820 2
388912 451197 1
18097 940244 1
935826 118218 2
938400 902754 1
122238 870886 1
25129...

output:

7 10 3 4 6 1 5 2 8 9 
4 9 8 5 10 1 2 6 3 7 
8 1 9 7 2 3 10 5 4 6 
6 7 1 9 10 5 8 3 2 4 
9 1 10 3 2 6 8 4 5 7 
9 1 6 3 2 4 8 5 7 10 
3 5 2 4 10 6 8 9 1 7 
8 4 2 1 6 10 9 3 5 7 
1 2 5 10 4 6 7 9 3 8 
10 7 8 1 5 2 3 9 6 4 
6 2 3 1 10 9 8 5 7 4 
6 7 4 10 3 8 5 9 2 1 
6 10 3 9 2 1 7 4 8 5 
3 1 10 9 8 6 7...

result:

ok correct

Test #62:

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

input:

5000
20
656459 452834 1
778773 545163 2
572641 540900 1
842346 965047 1
740062 319785 1
897329 270273 1
582655 610886 2
219885 724612 1
302339 486873 2
617143 729032 1
522655 412953 2
661512 656038 1
846755 641762 1
587397 69311 2
611884 874240 1
626444 442462 1
190156 648572 1
115134 369706 2
29791...

output:

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

result:

ok correct

Test #63:

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

input:

2000
50
801788 51391 2
351619 948789 1
452484 408774 1
51129 420086 2
308005 487650 1
124087 526739 1
834500 59027 2
194160 315058 1
801114 736832 2
399013 371746 2
385656 182930 2
165701 991455 1
960191 403475 2
893252 666759 2
519327 124615 2
408698 349786 2
71504 787913 2
28414 641975 2
694670 33...

output:

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

result:

ok correct

Test #64:

score: 0
Accepted
time: 584ms
memory: 3544kb

input:

20000
5
349635 545372 3
579595 140692 1
179577 639115 1
506674 394126 2
940918 984665 1
5
722719 738832 1
340014 207497 2
332923 924970 1
83487 862401 1
360189 725288 3
5
644969 427979 1
932260 540143 1
529066 41164 3
41527 594517 2
151518 802371 3
5
159420 223873 1
418549 425477 2
543863 175684 3
3...

output:

5 3 1 4 2 
1 3 4 5 2 
4 5 1 3 2 
2 1 3 5 4 
2 3 4 5 1 
4 1 5 3 2 
3 4 1 2 5 
4 3 1 2 5 
3 1 4 2 5 
5 3 1 4 2 
2 3 4 5 1 
3 5 4 2 1 
4 3 1 5 2 
5 3 2 1 4 
3 1 4 5 2 
1 2 4 3 5 
4 5 2 1 3 
5 4 3 1 2 
2 3 5 4 1 
5 1 2 4 3 
1 4 3 5 2 
2 1 3 5 4 
1 3 2 5 4 
2 5 4 3 1 
3 4 2 5 1 
1 5 3 4 2 
1 3 5 4 2 
4 5...

result:

ok correct

Test #65:

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

input:

10000
10
31727 221125 2
485566 191447 2
202614 823436 1
602000 665743 2
262468 951703 2
714165 270437 2
531329 587186 1
747707 733546 1
938995 511372 1
397787 143474 2
10
888810 580932 3
197190 87739 2
900778 251895 1
7027 924193 1
176286 474698 1
260070 240838 1
651514 688117 1
621058 218171 1
5601...

output:

7 3 1 5 4 2 6 10 8 9 
7 5 4 1 6 10 2 9 8 3 
8 6 4 9 1 2 3 5 10 7 
2 6 5 7 3 9 10 1 4 8 
6 8 3 1 4 2 10 9 7 5 
1 5 10 2 7 8 6 3 4 9 
7 3 6 5 1 4 9 10 2 8 
7 2 6 5 3 4 8 9 1 10 
8 9 5 7 10 6 3 4 1 2 
7 1 2 10 8 3 9 6 4 5 
7 10 4 9 8 1 2 5 3 6 
7 5 4 9 2 3 1 6 8 10 
3 9 8 7 6 5 2 4 10 1 
7 3 8 2 6 10 5...

result:

ok correct

Test #66:

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

input:

5000
20
693909 1678 3
224846 670224 1
506796 757592 2
402090 258190 3
934577 146219 3
144887 742187 3
646403 875127 3
61564 799418 2
396560 572889 1
917013 219152 1
864946 955927 3
31920 458147 1
466697 839133 3
205512 285412 1
770073 632887 2
917984 565082 1
870566 368527 2
613954 492800 3
606798 4...

output:

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

result:

ok correct

Test #67:

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

input:

2000
50
615046 600235 1
797692 265339 2
419343 592762 2
578169 647821 1
311033 281380 2
404349 774462 1
898248 323268 3
68543 389863 1
895335 47040 1
666180 53355 1
695243 693200 3
568813 793564 3
514725 600846 1
511367 882859 3
453324 659069 2
957134 696598 2
784617 349084 2
335747 765069 3
3557 65...

output:

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

result:

ok correct

Test #68:

score: 0
Accepted
time: 555ms
memory: 3540kb

input:

20000
5
176714 866987 8
970424 587123 8
543873 900795 2
303735 987914 7
206471 672631 8
5
210436 849621 3
318549 305954 10
364088 427550 7
677022 911826 1
812166 209585 1
5
964959 657626 9
777446 86692 1
667433 482872 3
116227 897704 10
248172 660801 5
5
210984 419727 8
401670 717513 2
2280 924253 5...

output:

3 4 5 1 2 
4 3 1 2 5 
5 4 3 1 2 
5 2 3 1 4 
4 3 5 1 2 
4 1 5 2 3 
2 5 3 4 1 
3 5 1 2 4 
3 4 5 2 1 
1 2 5 4 3 
1 4 2 5 3 
1 4 3 2 5 
4 5 2 1 3 
1 2 5 3 4 
4 2 1 5 3 
1 2 5 3 4 
2 3 4 5 1 
5 1 3 2 4 
3 4 5 1 2 
2 3 1 4 5 
5 3 1 4 2 
3 2 4 5 1 
5 2 4 1 3 
5 2 3 1 4 
5 1 3 4 2 
4 3 5 1 2 
5 4 1 2 3 
4 3...

result:

ok correct

Test #69:

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

input:

10000
10
654597 1459 1
923894 64902 6
262691 89248 7
358150 529230 3
901567 123793 5
980560 157661 6
959273 29856 6
325206 172317 3
949939 807372 2
838311 199219 4
10
233366 644854 1
190169 67417 7
501578 335259 6
659916 99903 7
932832 768340 8
532637 341539 2
933923 478859 10
860009 41454 1
838192 ...

output:

4 3 6 2 7 5 9 8 10 1 
1 10 7 2 5 3 6 9 4 8 
5 9 10 8 7 6 3 4 2 1 
4 9 1 5 2 6 7 3 8 10 
5 3 7 1 9 6 2 4 8 10 
2 1 3 5 8 10 4 9 6 7 
7 3 8 9 2 4 1 6 10 5 
10 1 7 2 3 4 9 8 6 5 
10 7 8 2 9 4 1 5 3 6 
6 2 3 4 10 5 9 1 7 8 
10 6 2 4 7 3 9 8 5 1 
9 6 7 8 1 10 5 3 2 4 
6 10 9 3 1 2 7 8 4 5 
9 7 4 2 3 8 10...

result:

ok correct

Test #70:

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

input:

5000
20
766765 821573 7
47152 486191 5
741809 250793 2
494657 103682 2
520073 351787 1
370366 397813 2
791833 85547 6
252430 700149 5
183656 1352 8
475996 193241 2
42735 344261 7
437697 193963 10
846433 698102 1
368303 134199 2
14203 150831 2
781792 422164 10
257358 840878 1
228671 452400 4
994250 6...

output:

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

result:

ok correct

Test #71:

score: 0
Accepted
time: 453ms
memory: 3568kb

input:

2000
50
551654 768124 8
1249 880873 9
594844 861509 4
62962 285279 1
473702 685496 2
955461 566652 1
387626 514638 4
389108 797436 3
365897 998974 5
683773 983820 8
246649 732082 10
956088 382116 10
563431 660549 5
367385 171681 8
66828 522496 7
594665 210534 6
68879 735446 5
558849 428341 7
462426 ...

output:

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

result:

ok correct

Test #72:

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

input:

20000
5
669470 534462 55
468298 187490 100
206893 758201 69
258186 362898 8
533447 698201 12
5
206835 442012 95
883357 22359 38
289734 685854 60
377434 953917 12
563132 774370 51
5
76922 747947 92
275788 403255 42
514858 886474 19
715680 871956 43
223330 516686 67
5
779987 911593 14
190719 43058 93
...

output:

4 5 3 2 1 
5 3 4 1 2 
2 4 5 3 1 
1 3 2 5 4 
1 2 4 5 3 
4 1 3 5 2 
3 2 5 4 1 
5 2 1 3 4 
4 2 3 5 1 
5 4 1 3 2 
1 2 3 4 5 
1 5 4 3 2 
3 1 2 5 4 
1 3 4 2 5 
3 5 4 1 2 
1 4 3 5 2 
2 3 1 5 4 
5 1 3 4 2 
4 5 1 2 3 
2 3 5 1 4 
4 3 2 1 5 
2 1 5 3 4 
3 4 2 1 5 
5 1 2 3 4 
4 3 2 1 5 
3 4 5 1 2 
5 3 1 2 4 
1 2...

result:

ok correct

Test #73:

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

input:

10000
10
536810 992362 99
761609 28053 47
155415 748533 83
494319 201328 24
91475 19752 47
405485 466162 99
655008 213674 23
444509 133342 33
525286 809425 82
613071 844672 49
10
666397 767595 49
297808 635481 42
221693 225482 46
315261 837455 15
565352 574158 82
267913 12243 79
862997 308727 33
131...

output:

10 3 9 6 1 5 4 8 7 2 
3 8 1 5 2 4 9 10 6 7 
5 9 10 7 2 4 3 1 6 8 
8 7 2 6 3 9 5 1 4 10 
4 5 3 9 2 10 1 7 6 8 
3 6 10 8 9 2 4 1 5 7 
4 8 6 1 3 10 9 5 7 2 
6 1 5 9 3 2 8 7 10 4 
3 5 9 10 8 1 4 2 7 6 
6 9 1 10 4 7 2 5 3 8 
5 1 6 2 8 4 10 9 7 3 
3 2 5 7 4 10 8 6 9 1 
10 3 9 2 6 5 1 4 7 8 
7 5 10 8 4 2 6...

result:

ok correct

Test #74:

score: 0
Accepted
time: 456ms
memory: 3620kb

input:

5000
20
886064 846032 53
945597 832741 20
224366 85420 50
96560 34122 68
339197 691861 74
702430 864180 54
762518 137259 72
530525 447199 16
272302 234286 4
899149 331194 15
468506 711028 40
527883 470211 47
470498 791400 84
882420 970532 37
655267 135242 83
796380 478669 23
986091 751971 47
491854 ...

output:

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

result:

ok correct

Test #75:

score: 0
Accepted
time: 439ms
memory: 3632kb

input:

2000
50
709633 767169 14
530265 372883 38
38389 997966 21
286260 434393 3
339261 68316 31
303664 123642 20
828150 356401 13
526558 421474 50
934152 733061 67
205768 145769 22
131728 606733 18
218108 7104 59
567184 872132 96
518487 276387 85
695702 75389 61
830164 485115 47
836458 633318 88
282069 12...

output:

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

result:

ok correct

Extra Test:

score: 0
Extra Test Passed