QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#340202#7777. Intro: Dawn of a New EragoodierTL 649ms92900kbC++175.7kb2024-02-28 18:45:112024-10-13 20:50:57

Judging History

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

  • [2024-10-13 20:50:57]
  • 管理员手动重测本题所有得分≥97分的提交记录
  • 测评结果:TL
  • 用时:649ms
  • 内存:92900kb
  • [2024-09-26 21:17:57]
  • hack成功,自动添加数据
  • (/hack/919)
  • [2024-09-26 21:13:28]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:97
  • 用时:636ms
  • 内存:92896kb
  • [2024-09-26 21:11:59]
  • hack成功,自动添加数据
  • (/hack/918)
  • [2024-02-28 18:45:11]
  • 评测
  • 测评结果:100
  • 用时:814ms
  • 内存:73576kb
  • [2024-02-28 18:45:11]
  • 提交

answer

#include <bits/stdc++.h>

#define x first
#define y second
#define mp make_pair

using namespace std;
typedef pair<int,int> PII;
const int N = 1e5 + 10, INF = 1e8;

vector <int> s[N];
int mx[N], n, b[2 * N], totb;
map <int, int> mp1;

int val(int x)
{
    return lower_bound(b + 1, b + totb + 1, x) - b;
}

namespace Dinic{
    const int N = 500010, M = 2400100, ss = N - 4, tt = N - 3;
    int head[N], ver[M], Next[M], edge[M], edge2[M], S, T, tot = 1, a[N], cnt, nxt[N], v[N];
    int cur[N], d[N];
    PII c[N], e[N];
    vector <int> G1[N], G2, G3[N];

    void add2(int x, int y, int z)
    {
        ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot;
        ver[++tot] = x, edge[tot] = 0, Next[tot] = head[y], head[y] = tot;
        //cout << x << " " << y << " " << z << endl;
    }

    void add(int x, int y, int z1, int z2)
    {
        ver[++tot] = y, edge[tot] = z1 - z2, edge2[tot] = z2, Next[tot] = head[x], head[x] = tot;
        ver[++tot] = x, edge[tot] = 0, edge2[tot] = z2, Next[tot] = head[y], head[y] = tot;
        a[x] += z2, a[y] -= z2;
        //cout << x << " " << y << " " << z1 << " " << z2 << endl;
    }

    void resume()
    {
        for(int i = 2; i <= tot; i += 2)
        {
            edge[i ^ 1] += edge2[i];
        }
        for(int i = 2; i <= 2 * n; i += 2)
        {
            int z = edge[i ^ 1];
            if(z) c[++cnt] = mp(ver[i ^ 1], ver[i] - n);
        }
    }

    bool cmpy(PII a, PII b)
    {
        return a.y < b.y;
    }

    int bfs()
    {
        queue <int> q;
        q.push(S);
        memset(d, -1, sizeof(d));
        d[S] = 0, cur[S] = head[S];
        while(!q.empty())
        {
            int x = q.front(); q.pop();
            for(int i = head[x]; i; i = Next[i])
            {
                int y = ver[i], z = edge[i];
                if(d[y] == -1 && z)
                {
                    d[y] = d[x] + 1;
                    cur[y] = head[y];
                    q.push(y);
                    if(y == T) return 1;
                }
            }
        }
        return 0;
    }

    int find(int x, int limit)
    {
        if(x == T) return limit;
        int flow = 0;
        for(int i = cur[x]; i && flow < limit; i = Next[i])
        {
            cur[x] = i;
            int y = ver[i], z = edge[i];
            if(d[y] == d[x] + 1 && z)
            {
                int t = find(y, min(z, limit - flow));
                if(!t) d[y] = -1;
                edge[i] -= t, edge[i ^ 1] += t, flow += t;
            }
        }
        return flow;
    }

    int dinic()
    {
        int r = 0, flow;
        while(bfs())
        {
            while(flow = find(S, INF))
            {
                r += flow;
            }
        }
        return r;
    }

    void solve()
    {
        S = N - 2, T = N - 1;
        for(int i = 1; i <= n + totb + totb; i++)
        {
            if(a[i] < 0) add2(S, i, -a[i]);
            else add2(i, T, a[i]);
        }
        add(tt, ss, INF, 0);
        dinic();
        int flow = edge[tot];
        edge[tot - 1] = edge[tot] = 0;
        S = tt, T = ss;
        flow -= dinic();
        printf("%d\n", n - flow);

        resume();
        sort(c + 1, c + cnt + 1, cmpy);
        for(int j = 1; j <= cnt; j++)
        {
            int x = c[j].x;
            v[x] = 1;
            for(int i = head[x]; i; i = Next[i])
            {
                if((i & 1) && edge[i])
                {
                    int pre = ver[i];
                    if(pre != ss)
                    {
                        pre = pre - n - totb;
                        int p = G1[pre][G1[pre].size() - 1]; G1[pre].pop_back();
                        nxt[p] = x;
                    }
                }
            }
            G1[mx[x]].push_back(x);
        }
        for(int x = 1; x <= n; x++)
        {
            if(!v[x])
            {
                G3[mx[x]].push_back(x);
            }
        }
        for(int i = 1; i <= n; i++) v[i] = 0;
        for(int j = 1; j <= cnt; j++)
        {
            int i = c[j].x;
            if(v[i]) continue;
            while(i)
            {
                G2.push_back(i);
                for(auto& p : G3[mx[i]]) G2.push_back(p);
                G3[mx[i]].clear();
                v[i] = 1;
                i = nxt[i];
            }
        }
        for(auto& p : G2) printf("%d ", p);
        return;
    }
}

int main()
{
    //freopen("data.in", "r", stdin);
    //freopen("data.out", "w", stdout);
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        int sz, x; scanf("%d", &sz);
        while(sz--)
        {
            scanf("%d", &x);
            s[i].push_back(x);
            b[++totb] = x;
        }
    }
    sort(b + 1, b + totb + 1);
    totb = unique(b + 1, b + totb + 1) - b - 1;
    for(int i = 1; i <= n; i++)
    {
        for(auto& x : s[i])
        {
            x = val(x);
            mx[i] = max(mx[i], x);
        }
        mp1[mx[i]] = 1;
    }
    for(int i = 1; i <= n; i++)
    {
        Dinic::add(i, n + mx[i], 1, 0);
    }
    for(int j = 1; j <= totb; j++)
    {
        Dinic::add(n + j, n + totb + j, INF, mp1[j]);
    }
    for(int i = 1; i <= n; i++)
    {
        for(auto& x : s[i])
        {
            if(x != mx[i])
            {
                Dinic::add(n + totb + x, i, 1, 0);
            }
        }
    }
    for(int i = 1; i <= n; i++)
    {
        Dinic::add(Dinic::ss, i, 1, 0);
    }
    for(int j = 1; j <= totb; j++)
    {
        Dinic::add(n + totb + j, Dinic::tt, INF, 0);
    }
    Dinic::solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 11ms
memory: 53012kb

input:

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

output:

3
4 2 3 1 5 

result:

ok correct!

Test #2:

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

input:

3
1 1
1 2
1 3

output:

0
1 2 3 

result:

ok correct!

Test #3:

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

input:

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

output:

7
1 8 7 9 2 4 3 5 6 

result:

ok correct!

Test #4:

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

input:

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

output:

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

result:

ok correct!

Test #5:

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

input:

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

output:

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

result:

ok correct!

Test #6:

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

input:

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

output:

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

result:

ok correct!

Test #7:

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

input:

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

output:

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

result:

ok correct!

Test #8:

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

input:

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

output:

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

result:

ok correct!

Test #9:

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

input:

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

output:

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

result:

ok correct!

Test #10:

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

input:

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

output:

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

result:

ok correct!

Test #11:

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

input:

20
2 13 20
2 16 20
2 20 21
2 4 5
2 16 21
2 11 13
2 5 7
2 16 19
2 18 19
2 12 18
2 1 16
2 11 17
2 11 20
2 2 19
2 6 20
2 19 20
2 4 13
2 17 20
2 14 17
2 15 17

output:

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

result:

ok correct!

Test #12:

score: 0
Accepted
time: 3ms
memory: 52976kb

input:

20
2 15 17
2 10 19
2 9 11
2 19 20
2 2 17
2 15 17
2 17 18
2 1 13
2 16 17
2 4 13
2 4 9
2 11 21
2 8 17
2 8 21
2 16 17
2 5 21
2 1 2
2 2 6
2 8 20
2 18 21

output:

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

result:

ok correct!

Test #13:

score: 0
Accepted
time: 6ms
memory: 55312kb

input:

20
2 4 16
2 11 18
2 16 18
2 20 21
2 18 21
2 13 18
2 15 17
2 3 13
2 16 19
2 3 19
2 13 20
2 9 19
2 19 21
2 8 12
2 10 14
2 12 18
2 11 20
2 11 16
2 16 20
2 17 20

output:

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

result:

ok correct!

Test #14:

score: 0
Accepted
time: 3ms
memory: 50888kb

input:

20
2 7 20
2 5 18
2 12 19
2 3 12
2 13 19
2 1 2
2 11 19
2 19 21
2 5 16
2 12 14
2 3 20
2 17 19
2 20 21
2 1 2
2 3 18
2 14 16
2 2 11
2 12 13
2 10 14
2 3 19

output:

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

result:

ok correct!

Test #15:

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

input:

20
2 7 11
2 11 17
2 9 21
2 1 2
2 15 19
2 9 21
2 1 10
2 7 19
2 17 21
2 15 17
2 7 9
2 20 21
2 1 5
2 14 17
2 14 21
2 10 21
2 6 20
2 7 9
2 4 6
2 17 18

output:

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

result:

ok correct!

Test #16:

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

input:

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

output:

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

result:

ok correct!

Test #17:

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

input:

1000
2 926 927
2 660 661
2 142 143
2 43 44
2 199 200
2 80 81
2 132 133
2 614 615
2 500 501
2 173 174
2 804 805
2 22 23
2 358 359
2 553 554
2 974 975
2 31 32
2 969 970
2 847 848
2 857 858
2 284 285
2 244 245
2 649 650
2 84 85
2 890 891
2 382 383
2 575 576
2 936 937
2 858 859
2 921 922
2 211 212
2 327...

output:

999
248 712 884 682 508 455 916 411 403 992 128 828 690 628 959 497 324 639 898 272 960 12 542 760 663 709 596 998 95 963 16 815 900 745 374 664 243 896 700 832 77 448 4 333 568 829 49 308 679 420 984 479 490 133 487 680 186 659 395 811 290 797 199 307 350 718 620 742 874 314 426 294 886 518 351 972...

result:

ok correct!

Test #18:

score: 0
Accepted
time: 6ms
memory: 51048kb

input:

1000
2 1 23
2 1 983
2 1 460
2 1 171
2 1 34
2 1 516
2 1 437
2 1 823
2 1 546
2 1 37
2 1 914
2 1 609
2 1 757
2 1 96
2 1 39
2 1 646
2 1 574
2 1 443
2 1 651
2 1 257
2 1 557
2 1 533
2 1 213
2 1 611
2 1 787
2 1 238
2 1 896
2 1 552
2 1 850
2 1 714
2 1 61
2 1 218
2 1 179
2 1 192
2 1 836
2 1 568
2 1 279
2 1 3...

output:

0
434 720 736 557 375 161 404 945 806 891 833 866 900 598 271 338 908 923 795 408 329 1 632 489 703 949 305 235 339 515 182 183 5 152 308 10 432 15 906 589 195 263 874 640 518 870 135 173 850 146 532 920 332 122 647 748 868 722 429 31 592 909 168 63 458 352 97 90 240 108 665 134 513 277 106 355 399 ...

result:

ok correct!

Test #19:

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

input:

1000
2 322 639
2 960 978
2 28 258
2 891 900
2 121 546
2 768 792
2 330 497
2 290 711
2 752 932
2 145 148
2 978 1000
2 96 644
2 326 892
2 292 961
2 285 348
2 312 858
2 222 509
2 342 944
2 305 361
2 266 831
2 521 906
2 701 908
2 238 473
2 345 589
2 899 932
2 4 490
2 780 905
2 786 790
2 952 956
2 170 55...

output:

759
59 606 529 12 540 617 715 825 925 381 386 173 691 349 567 771 319 10 609 517 703 912 187 30 809 669 562 375 574 100 495 987 842 423 931 880 365 762 945 9 25 722 796 286 479 708 237 179 532 659 368 89 61 969 199 267 584 1000 447 832 850 962 272 628 412 357 589 999 748 814 79 744 778 482 1 449 731...

result:

ok correct!

Test #20:

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

input:

1000
2 1 534
2 628 1001
2 498 1001
2 1 107
2 355 1001
2 1 313
2 756 1001
2 800 801
2 816 1001
2 972 1001
2 793 794
2 1 484
2 653 1001
2 1 664
2 920 921
2 992 993
2 1 931
2 1 576
2 1 761
2 1 682
2 835 1001
2 196 1001
2 1 608
2 790 1001
2 1 424
2 1 9
2 901 902
2 77 78
2 907 908
2 1 700
2 1 59
2 1 379
...

output:

541
900 274 254 313 964 113 26 901 667 675 923 423 991 286 870 946 696 546 317 909 662 289 614 153 830 911 867 72 958 707 152 412 176 616 405 335 262 927 604 161 936 668 31 770 829 772 305 52 980 245 819 207 151 850 442 74 28 483 669 680 392 173 729 255 618 187 447 752 847 454 98 826 575 4 798 816 3...

result:

ok correct!

Test #21:

score: 0
Accepted
time: 3ms
memory: 53040kb

input:

1000
2 507 536
2 995 999
2 447 844
2 673 963
2 236 608
2 621 897
2 622 748
2 984 991
2 219 719
2 40 994
2 643 717
2 642 754
2 812 867
2 42 369
2 659 998
2 307 359
2 366 816
2 270 441
2 86 216
2 918 929
2 433 651
2 622 927
2 162 416
2 422 593
2 329 575
2 925 948
2 841 869
2 339 576
2 178 342
2 548 79...

output:

749
617 591 374 788 526 933 303 588 658 469 616 61 871 295 157 136 704 997 649 318 980 286 961 688 245 744 419 408 760 411 894 748 331 787 306 816 732 979 274 903 390 693 717 55 182 138 865 964 884 118 460 333 19 906 807 335 595 679 791 208 799 745 246 73 190 224 273 585 753 15 148 257 260 500 2 49 ...

result:

ok correct!

Test #22:

score: 0
Accepted
time: 3ms
memory: 53352kb

input:

1000
2 9 630
2 20 209
2 886 910
2 229 395
2 775 876
2 53 785
2 116 539
2 541 947
2 440 878
2 348 541
2 62 72
2 185 207
2 457 478
2 876 943
2 289 828
2 199 569
2 750 866
2 350 859
2 449 1000
2 614 919
2 159 576
2 860 863
2 523 640
2 90 673
2 678 695
2 195 297
2 952 968
2 755 932
2 551 884
2 585 778
2...

output:

742
411 525 11 352 745 54 205 559 321 40 396 943 226 568 843 67 41 706 144 5 14 44 183 661 182 677 117 781 236 880 928 576 170 560 994 701 350 750 397 392 12 980 199 555 49 370 395 25 887 988 2 916 340 791 846 98 376 743 674 637 906 224 924 697 219 952 655 828 82 495 636 643 105 64 246 801 886 970 9...

result:

ok correct!

Test #23:

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

input:

1000
2 122 559
2 498 582
2 639 837
2 162 165
2 322 953
2 304 435
2 769 823
2 407 841
2 885 901
2 5 453
2 991 996
2 191 824
2 418 614
2 233 251
2 76 850
2 762 988
2 45 265
2 810 932
2 14 546
2 152 731
2 901 980
2 426 761
2 120 555
2 414 940
2 919 931
2 30 622
2 217 814
2 897 979
2 197 879
2 567 923
2...

output:

748
119 303 127 688 918 932 680 45 222 658 18 471 804 34 331 82 674 223 79 160 754 23 101 419 293 743 686 292 654 644 75 938 518 455 968 998 615 171 542 318 354 694 850 47 829 717 284 493 780 254 819 494 690 953 4 568 919 627 769 589 653 803 275 807 984 67 612 621 121 40 737 606 351 827 460 557 522 ...

result:

ok correct!

Test #24:

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

input:

1000
2 512697359 512774760
2 648164742 651715810
2 87626639 88106897
2 23746611 24188540
2 612369762 612453612
2 657545784 658170997
2 356463524 356849621
2 183720601 183734922
2 638606521 639379351
2 368881937 369615994
2 267253191 267995026
2 20605282 22822236
2 412174893 413053221
2 44459170 4470...

output:

999
535 176 467 282 495 466 353 550 470 604 906 568 710 19 868 748 701 57 334 849 656 636 128 587 873 622 459 146 12 76 692 4 108 159 659 314 996 826 967 920 551 411 624 973 192 431 812 225 25 553 647 227 573 687 594 752 390 613 274 536 558 725 841 330 888 53 420 988 629 59 951 14 252 58 468 190 97 ...

result:

ok correct!

Test #25:

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

input:

1000
2 689110 123618662
2 689110 377706241
2 689110 336058146
2 689110 420597240
2 689110 601454368
2 689110 217406459
2 689110 480517810
2 689110 123853154
2 689110 512642478
2 689110 434665274
2 689110 147499673
2 689110 502900373
2 689110 512082915
2 689110 528921552
2 689110 485324937
2 689110 4...

output:

0
162 561 401 559 786 72 69 380 439 671 725 115 906 169 718 612 986 460 547 462 331 770 663 477 414 785 778 977 239 576 355 53 889 498 661 656 258 203 58 583 727 548 501 373 505 183 118 748 91 235 210 487 318 345 139 597 359 892 59 109 497 187 704 449 873 899 845 696 956 314 21 83 858 99 698 266 539...

result:

ok correct!

Test #26:

score: 0
Accepted
time: 3ms
memory: 55156kb

input:

1000
2 13182656 97097493
2 534040646 686390939
2 15317349 798031669
2 12527965 844489633
2 571878710 942801249
2 209452489 642245523
2 309202234 665709291
2 452019901 817215335
2 213188968 660531281
2 236377020 719458791
2 885520813 929279023
2 789242396 954981032
2 728381185 905330516
2 930178744 9...

output:

629
220 1 957 524 544 374 486 735 382 60 173 461 587 332 864 515 429 786 361 733 866 586 812 135 797 224 300 719 100 520 216 561 438 763 845 842 67 445 391 801 897 459 185 751 741 80 494 772 305 188 714 335 72 604 590 21 972 887 713 994 287 641 960 396 167 978 116 527 70 869 657 418 238 566 43 413 4...

result:

ok correct!

Test #27:

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

input:

1000
2 234530151 645041705
2 541508343 541790009
2 475415737 477831954
2 403318 414196892
2 201373810 202813283
2 403318 101085488
2 249234594 645041705
2 403318 77381550
2 361905218 645041705
2 403318 46490445
2 126508755 645041705
2 403318 155549446
2 173971388 645041705
2 604500868 607164086
2 40...

output:

540
111 186 470 441 591 382 453 141 557 363 271 61 137 577 227 903 920 315 465 292 351 772 323 775 403 630 305 652 36 836 587 796 886 350 483 585 679 716 850 280 101 604 188 878 148 132 127 720 228 849 779 479 10 638 306 269 459 113 873 233 639 956 429 275 33 85 474 331 360 703 737 365 786 339 138 7...

result:

ok correct!

Test #28:

score: 0
Accepted
time: 7ms
memory: 53400kb

input:

1000
2 617243117 868238738
2 581179245 814192846
2 601381485 694795618
2 492520629 928681111
2 36607223 342636773
2 465170385 744208961
2 894226642 917965440
2 955758812 971948546
2 228214222 610889618
2 232507617 601381485
2 471311352 693868162
2 501068095 832083539
2 876843796 981863378
2 47083364...

output:

630
122 239 337 421 914 722 160 651 684 731 759 416 707 810 124 305 863 788 303 470 864 155 660 829 461 534 826 354 963 705 899 882 566 188 951 64 134 41 434 698 502 162 488 795 608 760 531 667 602 601 828 989 845 10 3 551 123 889 205 83 396 115 711 952 520 281 744 117 465 815 896 169 942 321 822 84...

result:

ok correct!

Test #29:

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

input:

1000
2 920901423 974010612
2 815808463 828407660
2 481347895 556221528
2 182460512 634505113
2 831483943 976133598
2 105815699 379285207
2 674221624 905477702
2 399113592 620489963
2 62016516 214067254
2 527579867 955151402
2 830675962 883173856
2 948490774 964039399
2 173305694 213392181
2 30615226...

output:

646
15 689 206 338 411 466 761 927 467 932 473 633 640 497 625 769 31 207 28 357 107 217 393 938 886 599 728 228 794 712 483 7 549 430 75 705 898 951 481 967 902 637 100 653 624 542 554 271 565 765 741 399 907 888 356 13 9 548 887 674 413 840 154 815 514 685 785 354 265 874 339 936 438 92 991 836 61...

result:

ok correct!

Test #30:

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

input:

1000
2 335179329 834946514
2 283244947 828406291
2 194193951 833817416
2 228853987 645842676
2 535125948 537666192
2 535369179 561139451
2 694701107 855227705
2 937751529 996625109
2 58635182 83954819
2 337719556 499663115
2 805571812 881156579
2 449637409 904707632
2 853294998 898929900
2 19747035 ...

output:

633
252 311 443 209 294 926 821 103 967 324 224 363 468 898 560 774 485 104 162 883 309 76 475 738 664 858 9 684 823 960 969 532 732 709 683 98 473 75 865 770 754 549 326 54 906 881 764 338 543 750 527 431 466 490 691 281 749 653 179 609 166 717 870 673 282 808 795 456 552 238 44 286 90 115 14 432 9...

result:

ok correct!

Test #31:

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

input:

100000
2 48459 48460
2 21895 21896
2 6640 6641
2 47086 47087
2 83937 83938
2 52096 52097
2 82721 82722
2 88798 88799
2 11916 11917
2 7382 7383
2 35078 35079
2 33960 33961
2 53910 53911
2 43673 43674
2 63314 63315
2 80238 80239
2 67146 67147
2 91456 91457
2 22355 22356
2 51033 51034
2 26479 26480
2 7...

output:

99999
76245 10773 13043 32899 88895 46371 81501 62284 4343 84490 94666 85913 12895 73843 51288 52503 8144 94154 30812 38356 91034 7625 28753 58842 5341 39356 93437 86033 53541 15209 43076 71407 81913 26821 46869 6551 89893 92879 88841 76700 54831 31493 42533 29537 48441 8495 21655 94082 39405 20952 ...

result:

ok correct!

Test #32:

score: 0
Accepted
time: 141ms
memory: 89792kb

input:

100000
2 1 81053
2 1 16517
2 1 90983
2 1 99752
2 1 85811
2 1 25069
2 1 93076
2 1 53744
2 1 53964
2 1 76157
2 1 60365
2 1 72282
2 1 86306
2 1 30379
2 1 50838
2 1 3764
2 1 75120
2 1 90708
2 1 2490
2 1 43799
2 1 77311
2 1 82055
2 1 8538
2 1 54162
2 1 56356
2 1 47484
2 1 9616
2 1 71534
2 1 68712
2 1 945...

output:

0
75333 39928 47811 67873 60774 32626 72485 12188 67181 5293 39465 90507 35566 69394 27866 13634 58733 66403 52861 60104 25487 81178 25564 79536 75143 67379 39735 78900 6304 25715 30297 49552 95857 93874 10059 28353 96609 92493 59976 61050 15280 53907 72307 21747 24655 44362 38464 91231 20668 84128 ...

result:

ok correct!

Test #33:

score: 0
Accepted
time: 324ms
memory: 89076kb

input:

100000
2 12000 54652
2 28351 79538
2 94360 94937
2 61977 85064
2 86167 86510
2 72079 81388
2 27376 95608
2 86518 89067
2 40238 45556
2 14542 19339
2 15897 35460
2 48661 50646
2 14032 44400
2 64328 70815
2 25376 99199
2 91299 95405
2 14847 99126
2 10716 70170
2 40377 72895
2 55068 87277
2 93035 95045...

output:

74529
69041 45805 85994 82789 90793 61504 68798 36638 64344 54664 35479 90702 40426 99674 17009 27759 7306 76416 56913 14511 62755 19841 85054 96019 43148 83783 2322 995 67352 38511 88030 28699 39759 19603 50696 71729 39188 14912 46913 71253 76378 24379 37365 50111 349 85542 77469 50984 50312 73143 ...

result:

ok correct!

Test #34:

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

input:

100000
2 1 12317
2 23106 100001
2 1 33767
2 47015 47016
2 74948 74949
2 1 27200
2 11084 11085
2 73463 100001
2 97529 97530
2 61168 100001
2 21246 21247
2 88781 100001
2 93455 100001
2 1 56715
2 1 59545
2 1 6644
2 61725 100001
2 37111 100001
2 1 59337
2 1 27135
2 42453 42454
2 5800 5801
2 22556 10000...

output:

55541
25761 54992 53526 43465 71704 87364 24895 21036 12093 65429 70884 22207 36737 16850 63872 51832 56146 79916 35897 58185 4203 99087 48782 99396 16226 47861 90885 30015 79251 73619 1586 37185 340 31386 62657 64588 2333 16602 1195 46909 41013 16039 47874 63124 20845 47917 95196 66302 78544 63503 ...

result:

ok correct!

Test #35:

score: 0
Accepted
time: 300ms
memory: 84040kb

input:

100000
2 42752 67631
2 97619 99412
2 64028 86492
2 60998 70996
2 71786 93438
2 74951 96860
2 78201 95252
2 51711 99890
2 5829 50791
2 79409 96439
2 70369 80364
2 95323 98450
2 23734 79022
2 49533 88776
2 63407 97283
2 10732 57041
2 5829 74062
2 61731 64329
2 10911 94555
2 41146 50147
2 91823 98918
2...

output:

74424
77402 5548 75630 37842 88692 13277 7562 89739 91965 8684 96694 93948 25227 159 29593 59780 33227 59417 32404 61384 96487 53681 55772 17067 9982 12011 14696 22081 96862 92086 11435 32693 41539 82481 91304 56003 2211 85542 48483 58074 15075 59344 71029 74178 99089 67602 49549 6117 9414 21394 245...

result:

ok correct!

Test #36:

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

input:

100000
2 13580 57952
2 88073 92336
2 40003 60273
2 37350 75834
2 33426 77751
2 44240 70645
2 4562 89897
2 79260 84075
2 11747 41473
2 27445 62209
2 67647 82594
2 64358 83057
2 56322 85247
2 63242 78982
2 91834 98455
2 66044 82898
2 73126 79954
2 54564 90545
2 36449 43667
2 53768 82955
2 33846 77078
...

output:

74529
71475 54534 95137 84765 59916 27222 8108 93278 36425 64075 96199 38477 67699 89828 51917 92575 70797 61336 78598 59641 75408 56947 84929 82508 2011 54495 49108 80335 85388 20616 18754 31522 62608 6510 23641 30803 32710 80682 21296 72870 57569 57950 76333 90157 18282 54424 90788 83737 91450 167...

result:

ok correct!

Test #37:

score: 0
Accepted
time: 316ms
memory: 85784kb

input:

100000
2 40228 81714
2 99713 99721
2 7259 32553
2 18515 59727
2 98969 99914
2 46923 54347
2 79489 99191
2 15790 28131
2 48637 70550
2 96452 97070
2 24912 25734
2 64363 77764
2 44429 68433
2 34796 74713
2 15622 35045
2 68822 73956
2 66344 93338
2 92871 97507
2 23587 80300
2 17611 74039
2 40450 94231
...

output:

74416
87188 1087 38319 1020 31359 95595 27272 27192 70137 82256 88884 30063 2185 15805 33255 7822 80631 11051 93830 76247 62850 20120 51608 58446 81666 97175 37474 4851 80269 93713 78073 54692 28418 28286 35445 97911 66643 77446 80790 58361 60966 61839 54056 711 39870 51473 59372 65000 85595 53452 2...

result:

ok correct!

Test #38:

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

input:

100000
2 596401419 596405347
2 31587562 31592900
2 253158848 253160067
2 654443478 654446953
2 260834303 260852020
2 461648137 461649937
2 61561195 61577827
2 116053155 116061032
2 476740816 476745660
2 598420085 598429594
2 453346816 453350408
2 494568528 494573032
2 487089527 487095168
2 247840352...

output:

99999
51068 49529 80796 86045 80411 33244 38458 29503 99284 34822 55740 34760 95335 97116 6336 44896 19267 38031 7300 36825 16575 53904 65563 72640 97880 35536 2904 84368 80065 15652 79218 85718 22663 83261 73079 51728 39760 3809 23097 58070 19815 23192 97961 81937 27021 72968 22487 70564 97702 2065...

result:

ok correct!

Test #39:

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

input:

100000
2 3142 140849999
2 3142 486848036
2 3142 99305595
2 3142 369542113
2 3142 130549827
2 3142 230567267
2 3142 114486183
2 3142 324385142
2 3142 523190768
2 3142 182822411
2 3142 287473472
2 3142 174863271
2 3142 418615430
2 3142 465179581
2 3142 5921085
2 3142 88494543
2 3142 279235795
2 3142 2...

output:

0
16720 37737 74113 76387 93322 15116 88160 6929 46117 69858 85524 91719 67407 43502 56044 9319 10830 433 57063 30697 75129 66878 64469 37613 12288 27752 368 50189 94370 43189 73431 3691 76395 77806 70771 96730 89713 37667 5539 72783 47316 51102 43333 99827 67494 47206 72412 93283 17234 42942 5151 2...

result:

ok correct!

Test #40:

score: 0
Accepted
time: 251ms
memory: 91040kb

input:

100000
2 237338344 652431151
2 773245782 995378876
2 524649543 738613984
2 366725068 885223820
2 810051474 872050776
2 972414208 992417952
2 883113760 888004022
2 155856635 723951012
2 421288306 886375493
2 5941848 229186961
2 416886098 673867373
2 157517412 371117347
2 849355506 895553328
2 2439590...

output:

63743
25687 80285 90517 88740 52280 50936 36871 48995 40241 57258 16696 10894 72428 72379 69449 91637 68833 84205 83744 15164 81138 61759 27039 2614 71774 58645 37581 70040 2768 3330 65657 75535 8926 26120 53848 37642 85851 77573 82933 1962 36765 1379 78037 30025 94685 15225 30009 57102 58772 79890 ...

result:

ok correct!

Test #41:

score: 0
Accepted
time: 148ms
memory: 91356kb

input:

100000
2 43890701 43901592
2 568 218118988
2 206823285 206829134
2 568 205642395
2 500741974 666071483
2 202032425 202033556
2 515527059 666071483
2 622229455 666071483
2 568 582113592
2 568 262721376
2 587512551 666071483
2 568 577191215
2 445248200 445248571
2 352847796 352857605
2 249588493 24959...

output:

55511
57181 41328 95112 27829 57148 6334 85215 78859 97048 34498 98663 62472 67244 72666 89211 18430 75111 75426 74204 5812 24399 79312 2164 18764 18674 85329 62212 9063 74242 89298 32314 55911 45838 11191 33991 42061 42786 23536 8381 49234 79560 58459 27269 81689 67677 89311 51297 73966 2613 74798 ...

result:

ok correct!

Test #42:

score: 0
Accepted
time: 256ms
memory: 90632kb

input:

100000
2 686849852 746248482
2 732526813 779294820
2 376786021 843151433
2 269957600 973473231
2 320069829 505476437
2 249208181 260879541
2 61651079 246358579
2 608000514 842597830
2 261154673 733548353
2 774471763 954541503
2 108045354 975764876
2 864725035 945036602
2 161286600 912396559
2 548794...

output:

63820
5927 7043 81345 30921 72599 48880 16709 89068 48042 91767 34634 11251 45164 78178 92233 83740 63871 69454 33288 30937 78570 94154 29928 79556 17961 11077 60732 40346 82333 67201 83999 22541 14197 61834 83276 82650 53510 42031 43368 77589 41229 17535 19458 68555 92085 95692 28569 89049 98151 31...

result:

ok correct!

Test #43:

score: 0
Accepted
time: 225ms
memory: 91576kb

input:

100000
2 702221799 829527113
2 594154243 730679644
2 698097756 958906217
2 790137799 913317707
2 301657172 552073583
2 337536232 371059060
2 389715331 682048619
2 988326494 993053331
2 159833625 861127609
2 652183344 821304427
2 679559260 807716233
2 380854425 911557959
2 292910660 384678167
2 11975...

output:

63840
27709 45589 41551 96976 33953 27166 87479 45358 2519 92540 46666 71710 58180 61925 98516 27103 25655 23917 46532 81786 93789 92794 65870 89314 99261 29123 78781 97935 6451 57816 64352 36327 85724 35504 63473 88570 73969 71070 84190 79100 74410 97193 4807 10391 42637 32110 14394 47633 25182 232...

result:

ok correct!

Test #44:

score: 0
Accepted
time: 258ms
memory: 87480kb

input:

100000
2 485070748 880630415
2 149909829 181582017
2 518889351 802876478
2 629244207 950379261
2 334862810 720985874
2 926637129 977914386
2 18740461 57165062
2 536638895 620961118
2 340803355 728643217
2 305158581 748948117
2 814938104 903197336
2 580779830 683888210
2 553576170 584700111
2 2906157...

output:

63859
36380 45723 97789 25388 42641 92560 39504 78849 95834 83135 89667 19945 66603 8031 99834 9325 50431 11301 96338 91471 93721 2972 86243 88858 65684 55174 62674 6923 44989 49104 79485 29783 34119 43182 19349 24260 15495 55600 36332 2270 63304 15017 75727 92257 51496 26654 5743 24722 36034 46871 ...

result:

ok correct!

Test #45:

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

input:

50000
4 45 60 36 68
2 18 29
3 78 27 73
2 17 37
5 39 49 45 68 74
3 45 88 36
5 77 70 38 28 1
4 71 0 40 18
6 91 49 27 7 38 31
3 73 45 47
3 8 21 65
1 98
6 42 70 9 41 62 0
5 42 79 39 37 31
3 74 100 17
3 95 31 87
5 51 48 32 72 69
2 92 87
1 72
5 98 33 13 28 18
3 98 42 33
5 93 85 100 5 69
3 94 6 88
4 87 81 ...

output:

49998
47772 2239 3999 4481 4900 4931 8348 8645 13736 15615 16292 16701 17151 20504 22558 23298 23881 24505 26379 26704 27067 28528 30038 30390 32989 36530 36818 37309 41264 43518 47758 46219 704 3209 7517 10218 15464 19007 20623 21813 22253 24050 24821 25949 27125 27663 27818 27928 29964 30335 31312...

result:

ok correct!

Test #46:

score: 0
Accepted
time: 177ms
memory: 63756kb

input:

50000
4 207 607 880 135
3 484 438 759
4 192 317 598 811
3 912 107 838
5 245 981 121 849 634
7 920 599 638 85 830 673 162
1 465
4 597 436 704 81
5 634 900 844 898 527
4 899 920 435 234
2 523 581
3 6 126 182
7 904 163 90 973 794 369 390
3 207 868 74
7 884 259 79 169 559 547 49
2 427 435
2 313 812
4 68...

output:

49934
38695 17704 18651 29962 20412 4904 43131 46899 38824 14152 17495 21401 8603 13993 42435 42184 1137 35746 36279 47732 47199 13752 28628 47137 31898 2695 9708 10836 17541 18032 18165 30707 37132 17773 18239 21892 34364 17806 42723 8348 4417 30385 18862 655 2013 8947 10198 17481 21496 22031 24844...

result:

ok correct!

Test #47:

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

input:

50000
3 1113 774 1032
3 1637 849 1523
2 1291 1960
5 737 376 438 1907 844
2 1657 1636
5 1252 1128 336 174 417
3 438 1645 364
5 1541 1594 821 1060 439
3 878 1043 1632
7 1506 1023 1734 1918 904 340 1213
2 1769 1778
5 1053 463 381 1348 395
3 323 1324 382
3 177 664 201
1 285
2 17 1159
3 1398 5 1465
4 834...

output:

49807
27918 13379 39612 20447 33400 48417 42440 1710 16761 19145 47019 47840 5548 9434 24031 38000 38251 41761 49387 49975 42954 1213 18684 24723 29494 31752 39207 43118 46056 49718 33735 8628 9948 23765 23897 24680 25488 34302 22998 2817 8477 9372 10329 12636 13551 15355 15830 16305 22208 27221 277...

result:

ok correct!

Test #48:

score: 0
Accepted
time: 264ms
memory: 63984kb

input:

50000
6 1932 2335 319 1627 1276 903
1 1074
4 3418 1963 2015 1396
3 423 2262 439
4 3261 1799 1742 854
4 2511 561 2598 1938
1 1609
4 2106 1519 3801 699
4 3822 2210 1792 2063
6 159 2986 2128 1072 3137 2632
4 1520 3179 2927 2523
6 549 1587 1568 3324 2096 1463
2 2671 1427
5 387 3441 1333 1212 2766
4 779 ...

output:

49508
29368 13939 4622 5132 6499 7809 34314 18185 48417 23555 38194 45964 47485 1401 18003 19664 45077 38635 26055 35951 25447 20982 22014 21915 35030 26010 2462 42836 22897 24065 38302 3776 12478 12927 14953 18938 26538 30131 34911 48101 46538 9048 10210 29908 30025 47918 3336 7125 7164 10813 17376...

result:

ok correct!

Test #49:

score: 0
Accepted
time: 299ms
memory: 64204kb

input:

50000
3 2180 4273 1595
1 2283
6 4115 4886 4931 5988 298 3993
6 2726 75 1258 5026 109 3702
5 4249 355 4095 4737 1812
7 5354 1250 1052 1931 4396 418 2218
3 791 1744 3896
3 1067 520 5278
2 1206 5518
6 4755 4598 3417 4111 4792 3796
3 2658 4809 27
5 1258 1959 2520 2410 1625
4 2772 3311 1798 111
5 2752 11...

output:

49185
40982 29361 28791 44993 8002 48746 4941 5054 40903 2436 361 381 2083 28738 47250 16955 9763 10855 49043 3171 5429 10802 28883 35957 39076 41867 32261 2956 5882 9911 12969 14990 19658 34888 36259 42246 45536 47844 45028 11189 21480 24127 25097 25125 25535 25679 26788 38605 44278 45178 48892 415...

result:

ok correct!

Test #50:

score: 0
Accepted
time: 304ms
memory: 64376kb

input:

50000
3 4868 1966 2385
4 2121 6317 2935 2319
3 5761 3025 6058
6 5262 7486 7357 6772 6784 1105
2 965 1435
4 2526 2549 1034 1014
4 7770 4679 1031 1226
6 976 7443 5675 3183 3319 1526
5 4613 5237 1010 7973 2692
1 3384
3 2999 406 1835
6 7582 3141 3671 1740 3375 5057
4 3165 2014 5380 4642
6 1824 174 6914 ...

output:

48824
10068 48982 5756 20784 39723 24631 1941 25020 15159 2507 7845 16363 34048 39028 43954 48206 19573 7249 264 17339 1694 18379 33815 15400 24283 25265 12265 10829 10936 19899 23110 23494 46444 7604 17324 34179 33627 20077 25511 45162 43673 3420 5326 12228 45776 49935 31972 44325 5425 6913 12668 3...

result:

ok correct!

Test #51:

score: 0
Accepted
time: 306ms
memory: 66552kb

input:

50000
4 7593 1614 9605 3123
3 3673 2818 30
2 3293 200
3 6148 3152 5348
6 1284 5233 1818 447 473 8712
4 963 4638 4061 2896
4 3079 6749 1264 9590
1 6966
3 285 8991 6853
3 6009 4660 5257
4 1667 1080 2569 4683
6 8720 9357 1826 4842 6282 1412
3 8047 3801 6251
4 892 7729 691 1327
7 9382 3872 5153 6802 236...

output:

48495
46921 4477 35662 31884 6466 22247 2670 40037 2323 19698 45093 20850 49693 1793 43887 6260 11322 37347 49266 49494 29782 21680 14344 31182 47444 10368 28 44421 37481 2403 7520 13242 15544 34075 39637 39682 15739 15469 21860 35458 42389 44354 46400 49649 29294 23447 26333 43315 48106 40051 6871 ...

result:

ok correct!

Test #52:

score: 0
Accepted
time: 323ms
memory: 67196kb

input:

50000
5 9084 8425 11202 11358 7066
3 5889 618 3445
5 73 8742 13869 14172 9580
3 2723 10630 5226
2 12195 70
6 12891 7338 5390 12082 5651 12757
5 8214 13218 334 3783 10040
5 11050 3018 14446 1828 2438
4 4179 5438 69 4249
5 2570 141 4446 5177 5018
5 10577 1120 3074 8618 8751
4 1847 11695 10989 8132
3 1...

output:

47582
26700 19747 29908 18055 45864 36609 4295 7355 12597 13823 16399 18659 20540 23313 31020 32852 46451 48569 18605 1902 7983 23722 44594 46634 48357 49017 42699 17660 19243 21077 23299 29549 36898 37577 44802 34044 857 2104 3526 5347 5457 9786 12485 16068 17178 20151 21449 23454 27770 28828 41567...

result:

ok correct!

Test #53:

score: 0
Accepted
time: 287ms
memory: 69356kb

input:

50000
4 347 9390 17911 5940
8 2485 523 15473 602 15622 18596 15924 2713
3 3418 18845 5746
4 17377 16407 15812 16142
4 6843 7050 4642 12056
4 17662 6811 19686 17426
7 4423 2905 17326 6735 12999 17264 18134
4 6381 529 12432 5042
8 4812 8415 2342 436 2646 7294 7391 9015
3 16712 13743 9802
3 19946 19519...

output:

46601
40959 49096 15983 30427 7442 22550 322 2164 16924 21929 4070 14575 24774 28935 32805 39731 41393 1309 3256 34390 36233 39624 40848 48059 11150 27915 17026 10837 44955 35946 11966 43435 14733 20182 31087 42249 5806 20259 23964 30907 44394 48082 49271 9771 29868 30417 37446 42155 7180 7644 15515...

result:

ok correct!

Test #54:

score: 0
Accepted
time: 331ms
memory: 69712kb

input:

50000
2 13646 8405
2 11353 10469
5 16080 22235 16681 23739 22080
2 12689 19542
4 10243 20288 22506 12090
3 12047 2856 456
2 17457 24668
6 5713 11086 22103 5218 19806 11314
4 11073 11885 13373 8871
5 4885 1937 16779 20998 23320
3 2832 9351 22420
4 9767 21633 22557 3387
4 6274 1841 2801 472
4 15542 11...

output:

45651
24512 45316 839 37659 18956 40378 3874 9268 23508 12433 30963 32779 38525 39060 6934 435 15788 18277 19303 24634 29483 32912 41075 42857 45598 46511 47768 49284 10165 25921 27250 30300 33024 41775 48957 22381 36021 16405 17391 23484 23633 36914 7392 48871 31832 29068 42217 13857 16738 926 1736...

result:

ok correct!

Test #55:

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

input:

100000
2 95 57
2 94 7
2 81 18
2 29 24
1 15
2 11 1
2 0 59
3 82 83 88
2 24 40
2 90 23
1 8
2 36 57
3 88 7 18
1 64
2 68 28
2 57 13
1 88
1 82
2 71 87
2 99 6
1 15
4 54 45 83 71
3 98 89 100
2 65 93
1 72
3 16 99 45
5 65 36 8 95 68
1 96
1 19
2 25 95
2 12 8
2 5 0
1 70
2 25 94
2 20 85
2 87 4
3 66 21 79
2 65 54...

output:

99999
99798 361 1014 1131 1252 1506 1733 1769 1953 2117 2351 2692 2931 3106 3153 3157 3173 3350 3528 3697 3999 4039 4439 4495 4809 4968 5035 5136 5191 5574 6459 6492 6818 6928 7305 7366 8633 8670 8697 8758 8821 9140 9268 9380 9513 10124 10302 10412 10643 10661 11007 11056 11330 12222 12282 12551 126...

result:

ok correct!

Test #56:

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

input:

100000
1 728
2 570 779
1 204
1 319
1 179
2 168 49
3 553 200 148
3 333 915 526
2 211 399
1 53
1 940
3 472 465 554
1 631
2 607 76
2 895 5
1 717
1 402
1 803
2 248 879
2 316 232
1 790
1 101
3 365 657 458
2 893 540
1 420
2 842 237
3 299 433 84
2 374 380
4 554 823 764 37
3 546 350 602
3 70 493 885
2 896 8...

output:

99977
98998 1893 3891 12450 24176 32943 33794 35669 35921 38305 42363 44725 47060 47480 48617 49487 52077 53104 63952 67956 68905 75833 76237 82165 87858 89005 90439 91951 94705 95504 98470 80933 639 2858 7746 11317 12211 12521 16119 19697 23497 25330 25606 27520 38173 43028 45369 50242 57355 59808 ...

result:

ok correct!

Test #57:

score: 0
Accepted
time: 475ms
memory: 71908kb

input:

100000
3 1673 1760 1959
3 1587 1262 1196
1 1692
2 685 333
1 1266
1 1726
1 150
2 562 455
2 1753 1222
3 94 1828 987
1 1581
1 1122
5 1172 1656 1619 1050 92
3 346 1421 1836
2 1726 315
3 174 1111 1716
2 460 1974
1 545
1 1772
3 397 1146 228
1 862
3 1658 1564 623
1 7
4 578 1344 190 1038
1 699
2 621 292
2 1...

output:

99920
95971 501 1624 2276 3419 3894 26476 30595 32924 36970 39996 45853 53283 59061 61018 66592 68652 81796 82948 93323 21024 341 13085 45472 48216 49793 50194 56926 59338 60388 64452 64737 72127 79718 98795 55334 3585 5495 7779 8975 24898 30490 38087 40478 43380 48185 49299 52708 56028 66643 73629 ...

result:

ok correct!

Test #58:

score: 0
Accepted
time: 600ms
memory: 71672kb

input:

100000
2 552 714
1 3933
4 432 2843 3596 2928
2 3538 1583
2 1030 3587
1 1403
2 485 3658
1 2496
3 1508 368 1426
2 629 704
1 892
2 3519 1658
3 1180 248 550
3 3367 1677 3703
2 3237 1548
4 678 283 3588 2431
1 3497
1 1423
3 1838 1657 935
4 1660 3924 431 1151
4 2507 1607 284 2371
1 2430
2 782 2666
1 3109
3...

output:

99719
67708 10807 18506 29126 62677 29461 1655 10448 15957 25386 30826 35050 45600 62492 73233 82558 86567 93178 96355 91131 4410 7158 22006 44946 45213 46562 57855 68346 70817 70965 88134 95440 96352 97855 48078 2252 14565 25598 29208 34224 47490 63471 82807 88456 56292 2421 10871 22429 24244 45649...

result:

ok correct!

Test #59:

score: 0
Accepted
time: 630ms
memory: 70460kb

input:

100000
1 2296
3 3934 3474 786
2 5866 5102
2 4440 1792
2 1259 869
2 3023 4842
2 3170 3000
2 413 2099
1 3773
1 4185
2 4726 5597
2 3898 5395
1 4124
1 1832
3 3915 501 4385
1 3790
1 2743
2 592 3352
1 744
1 5392
1 4274
1 4680
2 3719 2854
1 5368
1 4483
1 3742
1 3389
1 5183
1 3906
1 1687
1 2795
3 5557 5988 ...

output:

99411
96193 91741 65356 6738 8872 24739 55009 68363 1311 23433 26428 38156 42142 42460 45005 68103 92004 94138 84604 3954 4200 13967 25766 34385 41383 46283 55485 66110 74826 89668 97518 98016 15778 499 4014 7165 9233 37119 45648 46421 46579 61195 67677 77144 91231 96219 90576 1325 1976 6361 6708 12...

result:

ok correct!

Test #60:

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

input:

100000
2 865 6108
1 293
3 4957 7211 1105
2 1737 4288
1 7618
5 3380 6343 4662 3171 900
1 3940
2 7205 2620
2 7834 300
1 5447
1 1760
2 2046 2779
2 4550 509
1 966
1 7574
2 1127 5323
2 3662 2363
1 6609
5 6609 6120 2847 678 2649
2 6709 943
2 5439 3024
2 5502 4555
1 4127
2 1482 1692
4 2284 6117 5244 652
1 ...

output:

99035
63321 6629 32889 48216 52051 60418 72849 28420 29833 34962 35407 47093 66834 79267 82818 82833 84032 30618 3110 93240 18503 36483 42214 56410 95166 98235 13162 13813 21710 31840 38133 64411 81372 78262 14323 16060 39278 72314 83019 1210 7879 14013 16262 18615 18727 32324 34203 57324 62876 8172...

result:

ok correct!

Test #61:

score: 0
Accepted
time: 607ms
memory: 76544kb

input:

100000
2 5762 6767
2 8537 2102
2 607 6367
3 7112 7745 6439
4 4620 3044 6364 1337
3 8350 5196 3138
3 6950 1884 9531
2 229 5292
2 1327 2119
1 7918
1 5152
3 72 3285 7124
3 9899 4001 7613
3 4298 1244 4791
1 7457
1 28
5 951 9662 4572 3502 9680
1 2138
2 5651 9154
1 9360
3 1813 6018 9794
3 4245 4824 5268
1...

output:

98540
31491 3805 6137 7149 10622 71077 31119 16128 19120 24690 26661 77769 73372 26588 52660 69897 80267 94745 94440 8299 35695 90239 78542 10414 61942 70380 80136 90382 52640 11824 61590 65681 91083 98117 63353 23308 24734 50345 61412 63469 76541 78312 79794 88029 94255 73604 730 1108 1701 2018 561...

result:

ok correct!

Test #62:

score: 0
Accepted
time: 615ms
memory: 73336kb

input:

100000
1 11286
1 785
2 2239 7078
2 6616 8372
3 11324 13456 1784
1 7848
3 7628 474 3006
1 13935
3 12019 9631 4317
3 7682 4312 6157
2 11651 529
1 9630
1 13221
2 13870 5539
4 2192 164 14807 4346
5 9155 7210 13841 13429 13449
2 5021 4936
1 8822
2 12434 7739
2 5123 8562
3 1017 13118 9476
2 8039 4817
2 89...

output:

97114
47318 2290 84725 54277 58233 83897 63524 33280 12830 40981 60288 74168 78394 95802 9204 57181 62124 85954 86499 11129 40712 41594 56132 72303 80089 8431 19653 30228 35652 41133 49426 66082 74537 22175 5584 17264 35928 42582 60757 66353 74823 90518 99560 60489 6884 7750 12314 16053 21601 40359 ...

result:

ok correct!

Test #63:

score: 0
Accepted
time: 522ms
memory: 73704kb

input:

100000
1 3339
2 12542 1582
3 11876 1621 19577
3 3136 13480 6209
1 3391
1 15068
1 4363
1 16390
1 2717
2 11036 9644
2 19887 18032
1 17014
4 17213 9715 12377 19774
2 9019 3019
1 11718
3 19104 11059 18186
1 10481
2 13743 5146
4 17640 10057 19995 1096
1 749
3 5711 14461 10198
3 5238 12665 17485
1 4715
2 ...

output:

95363
76659 42189 63091 75566 50483 29578 38555 83689 92771 7072 41753 7325 10648 60791 89952 52122 11537 20760 32345 33501 45033 87380 2239 4509 20366 23539 54895 58972 77499 91097 46821 44212 44369 95666 28662 68326 12934 30422 30525 57174 59182 62881 96404 29748 20004 2600 6466 34609 48476 58942 ...

result:

ok correct!

Test #64:

score: 0
Accepted
time: 582ms
memory: 74060kb

input:

100000
1 22372
2 807 5345
1 1726
1 18351
1 18404
2 18059 21614
4 15502 10174 20082 19736
3 12777 11132 23474
3 21325 14585 6839
5 11249 2371 14077 1481 8214
2 10996 4408
2 12787 13372
2 11639 10240
2 19955 13988
2 18061 7646
2 18513 947
2 3721 5607
1 957
1 2616
1 23054
2 24206 247
2 10037 24755
2 30...

output:

93514
85057 6279 54497 2813 22758 76605 91341 42953 95838 26108 14293 16623 35215 52699 63211 571 3493 5744 76593 93945 82423 5521 42976 10709 26609 27615 36403 50937 13929 14550 55706 69323 77578 86028 7231 79450 2267 40087 7238 57845 64617 91088 46199 81862 89482 78973 10789 52000 17131 75146 3285...

result:

ok correct!

Test #65:

score: 0
Accepted
time: 88ms
memory: 87880kb

input:

2
199999 999936325 999932716 999907239 999936208 999842617 999852700 999975976 999934549 999950109 999989471 999836186 999912739 999898154 999941223 999804199 999930540 999981113 999969089 999802349 999906832 999873865 999939686 999927906 999921840 999878431 999866873 999935847 999964030 999950381 9...

output:

1
2 1 

result:

ok correct!

Extra Test:

score: -3
Extra Test Failed : Time Limit Exceeded on 3

input:

100000
2 5133 4551
2 8873 13905
2 16895 9092
2 18036 17939
2 10385 8455
2 10515 10242
2 5343 9491
2 18212 16191
2 14481 15198
2 19076 19423
2 14971 15987
2 5692 8273
2 14403 16840
2 17730 14989
2 3666 1229
2 9085 8082
2 2191 6310
2 9287 9727
2 9802 5161
2 2412 3966
2 15900 10882
2 15790 13806
2 9155...

output:


result: