QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#424706#7278. Brought Down the Grading Server?Lynkcat#70 562ms112848kbC++203.2kb2024-05-29 15:50:052024-05-29 15:50:08

Judging History

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

  • [2024-05-29 15:50:08]
  • 评测
  • 测评结果:70
  • 用时:562ms
  • 内存:112848kb
  • [2024-05-29 15:50:05]
  • 提交

answer

#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define sz(x) ((int)((x).size()))
#define int ll
// #define N 
using namespace std;
const int N=500005;
int cnt;
poly G[N];
vector<poly>a,b;
int vis[N];
pa E[N];
int egt;
poly Rt[N],Lf[N];
int n,m,q;
int DFN;
int dfn[N];
int id[N];
int pl[N],pr[N];
int val[N];
int du[N];
int ct[N];
void dfs(int i)
{
    while (G[i].size())
    {
        int u=G[i].back();G[i].pop_back();
        if (vis[u]) continue;
        vis[u]=1;
        int v=E[u].fi^E[u].se^i;
        dfs(v);
        // cout<<"vis "<<i<<"->"<<v<<" "<<val[v]<<endl;
        if (v==E[u].fi&&i!=cnt) Rt[v].push_back(i);
        else if (v!=cnt) Lf[i].push_back(v);
    }
}
void solve(int l,int r)
{
    if (l==r) return;
    int mid=l+(r-l)/2;

    cnt=n;
    ++DFN;
    egt=0;

    for (int i=1;i<=n;i++)
    {
        pl[i]=l;
        pr[i]=mid+1;
        for (int j=l;j<=r;j++)
        {
            if (ct[a[i][j]]) 
            {
                b[i][pl[i]++]=a[i][j];
                b[i][pr[i]++]=a[i][j];
            }
            ct[a[i][j]]^=1;
        }
        for (int j=l;j<=r;j++) 
        {
            if (ct[a[i][j]]) 
            {
                if (dfn[a[i][j]]!=DFN)
                {
                    dfn[a[i][j]]=DFN;
                    id[a[i][j]]=++cnt;
                    val[cnt]=a[i][j];
                }
                int u=id[a[i][j]];
                ++egt;
                E[egt]=mp(i,u);
                G[u].push_back(egt);
                G[i].push_back(egt);
                du[u]^=1,du[i]^=1;

                ct[a[i][j]]=0;
            }
        }
    }
    ++cnt;
    for (int i=1;i<cnt;i++) 
        if (du[i]) 
        {
            E[++egt]=mp(i,cnt);
            G[cnt].push_back(egt),G[i].push_back(egt);
        }
    for (int i=1;i<=cnt;i++) 
    {
        dfs(i);
        // cout<<endl;
    }
    for (int i=1;i<=n;i++)
    {
        // cout<<i<<","<<pl[i]<<" "<<pr[i]<<endl;
        for (auto u:Lf[i]) b[i][pl[i]++]=val[u];
        for (auto u:Rt[i]) b[i][pr[i]++]=val[u];
        assert(sz(Lf[i])==sz(Rt[i]));
        // cout<<i<<","<<sz(Lf[i])<<" "<<sz(Rt[i])<<endl;
        poly().swap(Lf[i]);
        poly().swap(Rt[i]);
    }
    for (int i=1;i<=egt;i++) vis[i]=0;
    for (int i=1;i<=cnt;i++) poly().swap(G[i]);
    for (int i=1;i<=n;i++)
        for (int j=l;j<=r;j++)
            a[i][j]=b[i][j];
    solve(l,mid);
    solve(mid+1,r);
}  
void BellaKira()
{
    cin>>n>>m>>q;
    a=vector<poly>(n+1,poly(m+1,0));
    b=a;
    for (int i=1;i<=n;i++)
        for (int j=0;j<m;j++)
            cin>>a[i][j];
    solve(0,m-1);
    for (int i=1;i<=n;i++)
    {
        for (int j=0;j<m;j++)
        {
            cout<<a[i][j]<<" ";
        }
        cout<<'\n';
    }
}
signed main()
{
    IOS;
    cin.tie(0);
    int T=1;
    while (T--)
    {
        BellaKira();
    }
}
/*list:
1.mod 998244353 or 1e9+7 or ???
2.N
3.duipai shuju xingtai duoyidian
...
*/

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 10
Accepted

Test #1:

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

input:

3 2 3
1 2
2 3
2 3

output:

2 1 
2 3 
3 2 

result:

ok 

Test #2:

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

input:

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

output:

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

result:

ok 

Test #3:

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

input:

20 2 12
12 11
1 9
12 12
3 4
3 9
8 3
8 11
10 9
4 3
6 7
11 6
11 3
7 10
12 10
11 10
11 11
11 2
1 12
6 12
2 7

output:

11 12 
9 1 
12 12 
3 4 
9 3 
3 8 
8 11 
10 9 
4 3 
6 7 
11 6 
11 3 
7 10 
12 10 
10 11 
11 11 
2 11 
1 12 
12 6 
7 2 

result:

ok 

Test #4:

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

input:

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

output:

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

result:

ok 

Test #5:

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

input:

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

output:

1 13 
14 4 
13 14 
17 1 
8 15 
14 5 
3 7 
6 20 
1 9 
11 19 
20 6 
13 11 

result:

ok 

Test #6:

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

input:

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

output:

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

result:

ok 

Test #7:

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

input:

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

output:

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

result:

ok 

Subtask #2:

score: 15
Accepted

Test #8:

score: 15
Accepted
time: 90ms
memory: 77300kb

input:

100000 2 100000
70318 14894
32116 90327
63866 29061
53683 63612
70370 78264
42647 76881
39251 31741
61186 66491
57686 65819
53278 59145
71962 26052
81040 55279
50859 51310
46800 24546
85013 91165
61530 21890
84003 29099
33573 86182
49212 10639
91851 97312
57682 14067
5243 69674
99007 62508
26290 555...

output:

14894 70318 
32116 90327 
63866 29061 
53683 63612 
70370 78264 
76881 42647 
39251 31741 
61186 66491 
65819 57686 
59145 53278 
26052 71962 
81040 55279 
50859 51310 
24546 46800 
91165 85013 
61530 21890 
29099 84003 
33573 86182 
10639 49212 
97312 91851 
14067 57682 
5243 69674 
99007 62508 
55...

result:

ok 

Test #9:

score: 0
Accepted
time: 47ms
memory: 77872kb

input:

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

output:

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

result:

ok 

Test #10:

score: 0
Accepted
time: 57ms
memory: 78144kb

input:

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

output:

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

result:

ok 

Test #11:

score: 0
Accepted
time: 73ms
memory: 76292kb

input:

98045 2 95001
27085 59126
75021 23663
67175 78883
3919 90698
20718 67504
49374 44011
1660 3236
71971 79270
24502 90540
54202 9732
14395 88659
56600 52635
21912 17986
92420 56526
40254 3472
64330 20431
9381 56003
57750 45529
45230 9388
83797 53437
75562 47526
63126 45219
71020 87437
50298 2016
21982 ...

output:

59126 27085 
23663 75021 
78883 67175 
3919 90698 
20718 67504 
44011 49374 
3236 1660 
79270 71971 
90540 24502 
9732 54202 
14395 88659 
56600 52635 
17986 21912 
92420 56526 
3472 40254 
20431 64330 
56003 9381 
45529 57750 
9388 45230 
53437 83797 
47526 75562 
63126 45219 
71020 87437 
2016 502...

result:

ok 

Test #12:

score: 0
Accepted
time: 84ms
memory: 65388kb

input:

89868 2 20001
16598 13223
18759 19981
2642 8681
4102 18080
11473 16749
690 15290
17900 16229
10684 17481
6328 12171
9417 1150
7185 5689
10346 17102
17958 9727
2117 13756
10955 13157
245 2840
5257 5337
16622 6429
17516 10772
13007 19349
11359 2821
14341 8897
3974 2482
16241 17966
18146 15458
3345 158...

output:

13223 16598 
19981 18759 
2642 8681 
18080 4102 
11473 16749 
15290 690 
16229 17900 
17481 10684 
6328 12171 
9417 1150 
5689 7185 
17102 10346 
9727 17958 
2117 13756 
13157 10955 
245 2840 
5337 5257 
6429 16622 
10772 17516 
19349 13007 
11359 2821 
8897 14341 
3974 2482 
17966 16241 
15458 1814...

result:

ok 

Test #13:

score: 0
Accepted
time: 48ms
memory: 68412kb

input:

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

output:

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

result:

ok 

Test #14:

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

input:

100000 2 100000
53479 25002
53479 63606
53479 40735
53479 83340
53479 40775
53479 11458
53479 8684
53479 60405
45116 53479
67722 53479
26014 53479
87860 53479
55147 53479
53479 22726
53479 67769
53479 129
14600 53479
53479 21514
53479 32164
60088 53479
53479 25415
70946 53479
53479 27091
33386 53479...

output:

25002 53479 
53479 63606 
53479 40735 
53479 83340 
53479 40775 
53479 11458 
53479 8684 
53479 60405 
53479 45116 
53479 67722 
53479 26014 
53479 87860 
53479 55147 
53479 22726 
53479 67769 
53479 129 
53479 14600 
53479 21514 
53479 32164 
53479 60088 
53479 25415 
53479 70946 
53479 27091 
5347...

result:

ok 

Test #15:

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

input:

100000 2 90000
8483 66963
63660 79073
41795 20397
1296 84311
3690 21178
21052 31611
51423 14323
34208 82468
83835 2785
50594 28274
59957 10993
34259 64334
89407 73934
14947 61083
53201 89472
61243 33351
76632 58718
67464 85318
54224 45096
84552 76529
44253 30697
43669 3108
26489 64691
79840 85776
76...

output:

66963 8483 
63660 79073 
41795 20397 
84311 1296 
3690 21178 
21052 31611 
51423 14323 
34208 82468 
2785 83835 
50594 28274 
59957 10993 
34259 64334 
73934 89407 
14947 61083 
53201 89472 
33351 61243 
58718 76632 
85318 67464 
45096 54224 
84552 76529 
30697 44253 
43669 3108 
64691 26489 
79840 ...

result:

ok 

Test #16:

score: 0
Accepted
time: 96ms
memory: 59596kb

input:

99458 2 99458
80944 83824
25208 26621
57146 28836
43915 18169
59242 47842
34224 78881
38791 20722
89723 91046
72800 40306
92681 94906
41151 7263
76035 13332
93928 38800
97168 86055
44186 73623
68071 7391
20692 72265
44111 42596
36037 77687
64592 836
43568 35187
34861 88539
37477 22111
85787 98028
73...

output:

83824 80944 
26621 25208 
28836 57146 
18169 43915 
47842 59242 
78881 34224 
20722 38791 
91046 89723 
40306 72800 
94906 92681 
7263 41151 
13332 76035 
38800 93928 
86055 97168 
73623 44186 
7391 68071 
72265 20692 
42596 44111 
77687 36037 
836 64592 
35187 43568 
88539 34861 
22111 37477 
98028...

result:

ok 

Test #17:

score: 0
Accepted
time: 57ms
memory: 81416kb

input:

100000 2 100000
91980 92592
12359 10704
35873 56718
28601 20301
78422 55548
74736 59974
81664 29025
55916 70432
47381 34185
31764 56168
33997 30947
70076 9029
52532 67057
79680 99273
54410 56704
45238 71652
12615 6894
66478 78041
40520 5451
58133 5950
89237 70551
36028 97551
83553 90630
15211 33690
...

output:

92592 91980 
12359 10704 
35873 56718 
28601 20301 
55548 78422 
74736 59974 
29025 81664 
70432 55916 
47381 34185 
56168 31764 
33997 30947 
70076 9029 
67057 52532 
99273 79680 
56704 54410 
45238 71652 
6894 12615 
66478 78041 
5451 40520 
5950 58133 
70551 89237 
97551 36028 
90630 83553 
33690...

result:

ok 

Test #18:

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

input:

99555 2 99555
79301 40457
40457 80634
49074 21580
92701 14354
44540 70461
47132 47637
84954 27979
87556 60683
22633 43063
49914 63643
4494 3571
88758 53632
17055 50019
49334 79039
67659 50111
17945 48061
84596 60323
14629 72033
77184 30069
64209 36217
49947 35279
45866 44707
58146 58484
1393 53385
4...

output:

40457 79301 
80634 40457 
21580 49074 
14354 92701 
70461 44540 
47637 47132 
27979 84954 
60683 87556 
22633 43063 
49914 63643 
3571 4494 
88758 53632 
50019 17055 
79039 49334 
50111 67659 
48061 17945 
84596 60323 
14629 72033 
30069 77184 
36217 64209 
35279 49947 
45866 44707 
58146 58484 
533...

result:

ok 

Subtask #3:

score: 5
Accepted

Dependency #2:

100%
Accepted

Test #19:

score: 5
Accepted
time: 94ms
memory: 80032kb

input:

100000 2 100000
70318 14894
32116 90327
63866 29061
53683 63612
70370 78264
42647 76881
39251 31741
61186 66491
57686 65819
53278 59145
71962 26052
81040 55279
50859 51310
46800 24546
85013 91165
61530 21890
84003 29099
33573 86182
49212 10639
91851 97312
57682 14067
5243 69674
99007 62508
26290 555...

output:

14894 70318 
32116 90327 
63866 29061 
53683 63612 
70370 78264 
76881 42647 
39251 31741 
61186 66491 
65819 57686 
59145 53278 
26052 71962 
81040 55279 
50859 51310 
24546 46800 
91165 85013 
61530 21890 
29099 84003 
33573 86182 
10639 49212 
97312 91851 
14067 57682 
5243 69674 
99007 62508 
55...

result:

ok 

Test #20:

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

input:

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

output:

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

result:

ok 

Test #21:

score: 0
Accepted
time: 47ms
memory: 76492kb

input:

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

output:

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

result:

ok 

Test #22:

score: 0
Accepted
time: 121ms
memory: 86664kb

input:

100000 2 100000
47641 2360
32311 27712
96580 5576
74432 69601
5497 90724
61408 72215
86499 23207
43465 29593
49534 20236
83680 95890
35990 98338
39222 14744
65183 72902
76527 73553
40936 27695
96356 68239
66861 20211
59817 9499
65669 53200
74170 53434
44590 79062
45816 66321
37251 32926
26433 58003
...

output:

2360 47641 
27712 32311 
5576 96580 
74432 69601 
5497 90724 
61408 72215 
86499 23207 
43465 29593 
20236 49534 
83680 95890 
98338 35990 
39222 14744 
65183 72902 
73553 76527 
40936 27695 
68239 96356 
20211 66861 
9499 59817 
53200 65669 
53434 74170 
79062 44590 
66321 45816 
32926 37251 
26433...

result:

ok 

Test #23:

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

input:

99000 2 100
50 76
35 53
70 8
48 61
12 98
81 72
62 87
10 6
61 83
63 42
66 10
7 46
35 66
47 52
30 60
70 33
27 16
32 82
8 28
85 83
95 21
63 84
47 57
89 86
73 69
52 60
72 78
78 61
61 36
3 73
31 50
47 20
69 28
74 34
100 79
99 56
51 43
86 15
38 28
3 94
63 76
19 56
31 90
79 97
3 23
14 44
78 63
99 85
14 50
...

output:

76 50 
35 53 
8 70 
61 48 
98 12 
72 81 
62 87 
10 6 
83 61 
63 42 
66 10 
7 46 
35 66 
52 47 
60 30 
70 33 
27 16 
32 82 
28 8 
85 83 
95 21 
63 84 
47 57 
86 89 
73 69 
60 52 
78 72 
61 78 
36 61 
3 73 
50 31 
47 20 
69 28 
74 34 
79 100 
56 99 
43 51 
15 86 
28 38 
94 3 
76 63 
19 56 
31 90 
97 7...

result:

ok 

Test #24:

score: 0
Accepted
time: 107ms
memory: 77256kb

input:

99000 2 40000
13317 12923
15159 469
15225 23585
11180 1824
7967 39735
13852 38886
33137 27292
21697 28740
9887 13116
25732 33405
9156 39496
24569 31286
12900 32138
2345 1862
18626 2824
19382 25016
11342 18721
10236 296
37626 8228
30418 10247
29998 33581
21676 4543
39650 14279
8842 1957
15206 22521
1...

output:

12923 13317 
15159 469 
15225 23585 
1824 11180 
39735 7967 
13852 38886 
27292 33137 
21697 28740 
9887 13116 
33405 25732 
9156 39496 
31286 24569 
12900 32138 
1862 2345 
2824 18626 
25016 19382 
18721 11342 
10236 296 
8228 37626 
10247 30418 
33581 29998 
4543 21676 
14279 39650 
8842 1957 
152...

result:

ok 

Test #25:

score: 0
Accepted
time: 97ms
memory: 75872kb

input:

98045 2 95001
27085 59126
75021 23663
67175 78883
3919 90698
20718 67504
49374 44011
1660 3236
71971 79270
24502 90540
54202 9732
14395 88659
56600 52635
21912 17986
92420 56526
40254 3472
64330 20431
9381 56003
57750 45529
45230 9388
83797 53437
75562 47526
63126 45219
71020 87437
50298 2016
21982 ...

output:

59126 27085 
23663 75021 
78883 67175 
3919 90698 
20718 67504 
44011 49374 
3236 1660 
79270 71971 
90540 24502 
9732 54202 
14395 88659 
56600 52635 
17986 21912 
92420 56526 
3472 40254 
20431 64330 
56003 9381 
45529 57750 
9388 45230 
53437 83797 
47526 75562 
63126 45219 
71020 87437 
2016 502...

result:

ok 

Test #26:

score: 0
Accepted
time: 95ms
memory: 70500kb

input:

89868 2 20001
16598 13223
18759 19981
2642 8681
4102 18080
11473 16749
690 15290
17900 16229
10684 17481
6328 12171
9417 1150
7185 5689
10346 17102
17958 9727
2117 13756
10955 13157
245 2840
5257 5337
16622 6429
17516 10772
13007 19349
11359 2821
14341 8897
3974 2482
16241 17966
18146 15458
3345 158...

output:

13223 16598 
19981 18759 
2642 8681 
18080 4102 
11473 16749 
15290 690 
16229 17900 
17481 10684 
6328 12171 
9417 1150 
5689 7185 
17102 10346 
9727 17958 
2117 13756 
13157 10955 
245 2840 
5337 5257 
6429 16622 
10772 17516 
19349 13007 
11359 2821 
8897 14341 
3974 2482 
17966 16241 
15458 1814...

result:

ok 

Test #27:

score: 0
Accepted
time: 47ms
memory: 65140kb

input:

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

output:

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

result:

ok 

Test #28:

score: 0
Accepted
time: 97ms
memory: 74328kb

input:

100000 2 100000
53479 25002
53479 63606
53479 40735
53479 83340
53479 40775
53479 11458
53479 8684
53479 60405
45116 53479
67722 53479
26014 53479
87860 53479
55147 53479
53479 22726
53479 67769
53479 129
14600 53479
53479 21514
53479 32164
60088 53479
53479 25415
70946 53479
53479 27091
33386 53479...

output:

25002 53479 
53479 63606 
53479 40735 
53479 83340 
53479 40775 
53479 11458 
53479 8684 
53479 60405 
53479 45116 
53479 67722 
53479 26014 
53479 87860 
53479 55147 
53479 22726 
53479 67769 
53479 129 
53479 14600 
53479 21514 
53479 32164 
53479 60088 
53479 25415 
53479 70946 
53479 27091 
5347...

result:

ok 

Test #29:

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

input:

100000 2 90000
8483 66963
63660 79073
41795 20397
1296 84311
3690 21178
21052 31611
51423 14323
34208 82468
83835 2785
50594 28274
59957 10993
34259 64334
89407 73934
14947 61083
53201 89472
61243 33351
76632 58718
67464 85318
54224 45096
84552 76529
44253 30697
43669 3108
26489 64691
79840 85776
76...

output:

66963 8483 
63660 79073 
41795 20397 
84311 1296 
3690 21178 
21052 31611 
51423 14323 
34208 82468 
2785 83835 
50594 28274 
59957 10993 
34259 64334 
73934 89407 
14947 61083 
53201 89472 
33351 61243 
58718 76632 
85318 67464 
45096 54224 
84552 76529 
30697 44253 
43669 3108 
64691 26489 
79840 ...

result:

ok 

Test #30:

score: 0
Accepted
time: 104ms
memory: 60888kb

input:

99458 2 99458
80944 83824
25208 26621
57146 28836
43915 18169
59242 47842
34224 78881
38791 20722
89723 91046
72800 40306
92681 94906
41151 7263
76035 13332
93928 38800
97168 86055
44186 73623
68071 7391
20692 72265
44111 42596
36037 77687
64592 836
43568 35187
34861 88539
37477 22111
85787 98028
73...

output:

83824 80944 
26621 25208 
28836 57146 
18169 43915 
47842 59242 
78881 34224 
20722 38791 
91046 89723 
40306 72800 
94906 92681 
7263 41151 
13332 76035 
38800 93928 
86055 97168 
73623 44186 
7391 68071 
72265 20692 
42596 44111 
77687 36037 
836 64592 
35187 43568 
88539 34861 
22111 37477 
98028...

result:

ok 

Test #31:

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

input:

100000 2 100000
91980 92592
12359 10704
35873 56718
28601 20301
78422 55548
74736 59974
81664 29025
55916 70432
47381 34185
31764 56168
33997 30947
70076 9029
52532 67057
79680 99273
54410 56704
45238 71652
12615 6894
66478 78041
40520 5451
58133 5950
89237 70551
36028 97551
83553 90630
15211 33690
...

output:

92592 91980 
12359 10704 
35873 56718 
28601 20301 
55548 78422 
74736 59974 
29025 81664 
70432 55916 
47381 34185 
56168 31764 
33997 30947 
70076 9029 
67057 52532 
99273 79680 
56704 54410 
45238 71652 
6894 12615 
66478 78041 
5451 40520 
5950 58133 
70551 89237 
97551 36028 
90630 83553 
33690...

result:

ok 

Test #32:

score: 0
Accepted
time: 58ms
memory: 78624kb

input:

99555 2 99555
79301 40457
40457 80634
49074 21580
92701 14354
44540 70461
47132 47637
84954 27979
87556 60683
22633 43063
49914 63643
4494 3571
88758 53632
17055 50019
49334 79039
67659 50111
17945 48061
84596 60323
14629 72033
77184 30069
64209 36217
49947 35279
45866 44707
58146 58484
1393 53385
4...

output:

40457 79301 
80634 40457 
21580 49074 
14354 92701 
70461 44540 
47637 47132 
27979 84954 
60683 87556 
22633 43063 
49914 63643 
3571 4494 
88758 53632 
50019 17055 
79039 49334 
50111 67659 
48061 17945 
84596 60323 
14629 72033 
30069 77184 
36217 64209 
35279 49947 
45866 44707 
58146 58484 
533...

result:

ok 

Subtask #4:

score: 5
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #33:

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

input:

3 2 3
1 2
2 3
2 3

output:

2 1 
2 3 
3 2 

result:

ok 

Test #34:

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

input:

89868 2 20001
16598 13223
18759 19981
2642 8681
4102 18080
11473 16749
690 15290
17900 16229
10684 17481
6328 12171
9417 1150
7185 5689
10346 17102
17958 9727
2117 13756
10955 13157
245 2840
5257 5337
16622 6429
17516 10772
13007 19349
11359 2821
14341 8897
3974 2482
16241 17966
18146 15458
3345 158...

output:

13223 16598 
19981 18759 
2642 8681 
18080 4102 
11473 16749 
15290 690 
16229 17900 
17481 10684 
6328 12171 
9417 1150 
5689 7185 
17102 10346 
9727 17958 
2117 13756 
13157 10955 
245 2840 
5337 5257 
6429 16622 
10772 17516 
19349 13007 
11359 2821 
8897 14341 
3974 2482 
17966 16241 
15458 1814...

result:

ok 

Test #35:

score: 0
Accepted
time: 28ms
memory: 72180kb

input:

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

output:

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

result:

ok 

Test #36:

score: 0
Accepted
time: 70ms
memory: 76116kb

input:

100000 2 100000
53479 25002
53479 63606
53479 40735
53479 83340
53479 40775
53479 11458
53479 8684
53479 60405
45116 53479
67722 53479
26014 53479
87860 53479
55147 53479
53479 22726
53479 67769
53479 129
14600 53479
53479 21514
53479 32164
60088 53479
53479 25415
70946 53479
53479 27091
33386 53479...

output:

25002 53479 
53479 63606 
53479 40735 
53479 83340 
53479 40775 
53479 11458 
53479 8684 
53479 60405 
53479 45116 
53479 67722 
53479 26014 
53479 87860 
53479 55147 
53479 22726 
53479 67769 
53479 129 
53479 14600 
53479 21514 
53479 32164 
53479 60088 
53479 25415 
53479 70946 
53479 27091 
5347...

result:

ok 

Test #37:

score: 0
Accepted
time: 105ms
memory: 78896kb

input:

100000 2 90000
8483 66963
63660 79073
41795 20397
1296 84311
3690 21178
21052 31611
51423 14323
34208 82468
83835 2785
50594 28274
59957 10993
34259 64334
89407 73934
14947 61083
53201 89472
61243 33351
76632 58718
67464 85318
54224 45096
84552 76529
44253 30697
43669 3108
26489 64691
79840 85776
76...

output:

66963 8483 
63660 79073 
41795 20397 
84311 1296 
3690 21178 
21052 31611 
51423 14323 
34208 82468 
2785 83835 
50594 28274 
59957 10993 
34259 64334 
73934 89407 
14947 61083 
53201 89472 
33351 61243 
58718 76632 
85318 67464 
45096 54224 
84552 76529 
30697 44253 
43669 3108 
64691 26489 
79840 ...

result:

ok 

Test #38:

score: 0
Accepted
time: 92ms
memory: 57644kb

input:

99458 2 99458
80944 83824
25208 26621
57146 28836
43915 18169
59242 47842
34224 78881
38791 20722
89723 91046
72800 40306
92681 94906
41151 7263
76035 13332
93928 38800
97168 86055
44186 73623
68071 7391
20692 72265
44111 42596
36037 77687
64592 836
43568 35187
34861 88539
37477 22111
85787 98028
73...

output:

83824 80944 
26621 25208 
28836 57146 
18169 43915 
47842 59242 
78881 34224 
20722 38791 
91046 89723 
40306 72800 
94906 92681 
7263 41151 
13332 76035 
38800 93928 
86055 97168 
73623 44186 
7391 68071 
72265 20692 
42596 44111 
77687 36037 
836 64592 
35187 43568 
88539 34861 
22111 37477 
98028...

result:

ok 

Test #39:

score: 0
Accepted
time: 55ms
memory: 78860kb

input:

100000 2 100000
91980 92592
12359 10704
35873 56718
28601 20301
78422 55548
74736 59974
81664 29025
55916 70432
47381 34185
31764 56168
33997 30947
70076 9029
52532 67057
79680 99273
54410 56704
45238 71652
12615 6894
66478 78041
40520 5451
58133 5950
89237 70551
36028 97551
83553 90630
15211 33690
...

output:

92592 91980 
12359 10704 
35873 56718 
28601 20301 
55548 78422 
74736 59974 
29025 81664 
70432 55916 
47381 34185 
56168 31764 
33997 30947 
70076 9029 
67057 52532 
99273 79680 
56704 54410 
45238 71652 
6894 12615 
66478 78041 
5451 40520 
5950 58133 
70551 89237 
97551 36028 
90630 83553 
33690...

result:

ok 

Test #40:

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

input:

99555 2 99555
79301 40457
40457 80634
49074 21580
92701 14354
44540 70461
47132 47637
84954 27979
87556 60683
22633 43063
49914 63643
4494 3571
88758 53632
17055 50019
49334 79039
67659 50111
17945 48061
84596 60323
14629 72033
77184 30069
64209 36217
49947 35279
45866 44707
58146 58484
1393 53385
4...

output:

40457 79301 
80634 40457 
21580 49074 
14354 92701 
70461 44540 
47637 47132 
27979 84954 
60683 87556 
22633 43063 
49914 63643 
3571 4494 
88758 53632 
50019 17055 
79039 49334 
50111 67659 
48061 17945 
84596 60323 
14629 72033 
30069 77184 
36217 64209 
35279 49947 
45866 44707 
58146 58484 
533...

result:

ok 

Test #41:

score: 0
Accepted
time: 36ms
memory: 79576kb

input:

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

output:

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

result:

ok 

Test #42:

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

input:

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

output:

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

result:

ok 

Test #43:

score: 0
Accepted
time: 87ms
memory: 86700kb

input:

100000 2 100000
47641 2360
32311 27712
96580 5576
74432 69601
5497 90724
61408 72215
86499 23207
43465 29593
49534 20236
83680 95890
35990 98338
39222 14744
65183 72902
76527 73553
40936 27695
96356 68239
66861 20211
59817 9499
65669 53200
74170 53434
44590 79062
45816 66321
37251 32926
26433 58003
...

output:

2360 47641 
27712 32311 
5576 96580 
74432 69601 
5497 90724 
61408 72215 
86499 23207 
43465 29593 
20236 49534 
83680 95890 
98338 35990 
39222 14744 
65183 72902 
73553 76527 
40936 27695 
68239 96356 
20211 66861 
9499 59817 
53200 65669 
53434 74170 
79062 44590 
66321 45816 
32926 37251 
26433...

result:

ok 

Test #44:

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

input:

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

output:

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

result:

ok 

Test #45:

score: 0
Accepted
time: 44ms
memory: 72916kb

input:

99000 2 100
50 76
35 53
70 8
48 61
12 98
81 72
62 87
10 6
61 83
63 42
66 10
7 46
35 66
47 52
30 60
70 33
27 16
32 82
8 28
85 83
95 21
63 84
47 57
89 86
73 69
52 60
72 78
78 61
61 36
3 73
31 50
47 20
69 28
74 34
100 79
99 56
51 43
86 15
38 28
3 94
63 76
19 56
31 90
79 97
3 23
14 44
78 63
99 85
14 50
...

output:

76 50 
35 53 
8 70 
61 48 
98 12 
72 81 
62 87 
10 6 
83 61 
63 42 
66 10 
7 46 
35 66 
52 47 
60 30 
70 33 
27 16 
32 82 
28 8 
85 83 
95 21 
63 84 
47 57 
86 89 
73 69 
60 52 
78 72 
61 78 
36 61 
3 73 
50 31 
47 20 
69 28 
74 34 
79 100 
56 99 
43 51 
15 86 
28 38 
94 3 
76 63 
19 56 
31 90 
97 7...

result:

ok 

Test #46:

score: 0
Accepted
time: 115ms
memory: 75616kb

input:

99000 2 40000
13317 12923
15159 469
15225 23585
11180 1824
7967 39735
13852 38886
33137 27292
21697 28740
9887 13116
25732 33405
9156 39496
24569 31286
12900 32138
2345 1862
18626 2824
19382 25016
11342 18721
10236 296
37626 8228
30418 10247
29998 33581
21676 4543
39650 14279
8842 1957
15206 22521
1...

output:

12923 13317 
15159 469 
15225 23585 
1824 11180 
39735 7967 
13852 38886 
27292 33137 
21697 28740 
9887 13116 
33405 25732 
9156 39496 
31286 24569 
12900 32138 
1862 2345 
2824 18626 
25016 19382 
18721 11342 
10236 296 
8228 37626 
10247 30418 
33581 29998 
4543 21676 
14279 39650 
8842 1957 
152...

result:

ok 

Test #47:

score: 0
Accepted
time: 51ms
memory: 56184kb

input:

50000 2 100000
98362 76208
42505 92719
18460 89381
66596 99759
12116 82137
92591 4043
134 72622
43432 47060
48543 74386
24648 12398
15658 30807
44636 99813
53782 10967
99129 43783
31224 17380
1594 90445
4363 11935
83427 79197
57698 64946
55536 76058
25332 10458
66313 31325
77601 43931
23727 27286
38...

output:

76208 98362 
42505 92719 
89381 18460 
99759 66596 
82137 12116 
4043 92591 
72622 134 
43432 47060 
48543 74386 
12398 24648 
30807 15658 
44636 99813 
53782 10967 
43783 99129 
31224 17380 
90445 1594 
11935 4363 
83427 79197 
64946 57698 
55536 76058 
10458 25332 
66313 31325 
43931 77601 
27286 ...

result:

ok 

Test #48:

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

input:

1000 2 90000
23815 25217
6968 45020
4010 7431
26939 4476
2589 64334
32215 84328
8428 78626
15793 9319
30520 48129
73647 7113
69869 35054
2118 65562
13093 15772
66586 74609
2641 56451
80789 47288
35419 63553
4412 70594
45845 37418
71587 74602
19228 59932
53972 84459
7561 23333
29074 12664
26734 61072...

output:

25217 23815 
6968 45020 
4010 7431 
26939 4476 
2589 64334 
32215 84328 
8428 78626 
15793 9319 
30520 48129 
73647 7113 
69869 35054 
2118 65562 
13093 15772 
66586 74609 
2641 56451 
80789 47288 
35419 63553 
4412 70594 
45845 37418 
71587 74602 
59932 19228 
53972 84459 
7561 23333 
29074 12664 
...

result:

ok 

Test #49:

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

input:

20 2 12
12 11
1 9
12 12
3 4
3 9
8 3
8 11
10 9
4 3
6 7
11 6
11 3
7 10
12 10
11 10
11 11
11 2
1 12
6 12
2 7

output:

11 12 
9 1 
12 12 
3 4 
9 3 
3 8 
8 11 
10 9 
4 3 
6 7 
11 6 
11 3 
7 10 
12 10 
10 11 
11 11 
2 11 
1 12 
12 6 
7 2 

result:

ok 

Test #50:

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

input:

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

output:

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

result:

ok 

Test #51:

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

input:

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

output:

1 13 
14 4 
13 14 
17 1 
8 15 
14 5 
3 7 
6 20 
1 9 
11 19 
20 6 
13 11 

result:

ok 

Test #52:

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

input:

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

output:

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

result:

ok 

Test #53:

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

input:

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

output:

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

result:

ok 

Test #54:

score: 0
Accepted
time: 103ms
memory: 76300kb

input:

100000 2 100000
70318 14894
32116 90327
63866 29061
53683 63612
70370 78264
42647 76881
39251 31741
61186 66491
57686 65819
53278 59145
71962 26052
81040 55279
50859 51310
46800 24546
85013 91165
61530 21890
84003 29099
33573 86182
49212 10639
91851 97312
57682 14067
5243 69674
99007 62508
26290 555...

output:

14894 70318 
32116 90327 
63866 29061 
53683 63612 
70370 78264 
76881 42647 
39251 31741 
61186 66491 
65819 57686 
59145 53278 
26052 71962 
81040 55279 
50859 51310 
24546 46800 
91165 85013 
61530 21890 
29099 84003 
33573 86182 
10639 49212 
97312 91851 
14067 57682 
5243 69674 
99007 62508 
55...

result:

ok 

Test #55:

score: 0
Accepted
time: 87ms
memory: 73532kb

input:

98045 2 95001
27085 59126
75021 23663
67175 78883
3919 90698
20718 67504
49374 44011
1660 3236
71971 79270
24502 90540
54202 9732
14395 88659
56600 52635
21912 17986
92420 56526
40254 3472
64330 20431
9381 56003
57750 45529
45230 9388
83797 53437
75562 47526
63126 45219
71020 87437
50298 2016
21982 ...

output:

59126 27085 
23663 75021 
78883 67175 
3919 90698 
20718 67504 
44011 49374 
3236 1660 
79270 71971 
90540 24502 
9732 54202 
14395 88659 
56600 52635 
17986 21912 
92420 56526 
3472 40254 
20431 64330 
56003 9381 
45529 57750 
9388 45230 
53437 83797 
47526 75562 
63126 45219 
71020 87437 
2016 502...

result:

ok 

Subtask #5:

score: 15
Accepted

Test #56:

score: 15
Accepted
time: 2ms
memory: 17920kb

input:

3 4 3
2 3 2 2
2 3 3 2
2 2 3 2

output:

3 2 2 2 
2 3 2 3 
2 2 3 2 

result:

ok 

Test #57:

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

input:

2450 4 2450
540 475 1156 2334
2421 2439 1328 750
471 1051 2007 1792
1776 786 705 2269
1277 755 1674 1622
590 1378 1217 603
967 239 1658 1920
857 2307 1589 78
2172 861 2322 1634
2077 2021 1381 2179
1126 345 1547 2126
994 1214 1477 412
1857 2085 831 978
281 1844 2406 2174
521 2334 2254 1779
1508 905 1...

output:

2334 475 1156 540 
750 2439 2421 1328 
2007 1051 1792 471 
786 2269 705 1776 
1277 1622 1674 755 
603 1217 1378 590 
1658 239 1920 967 
78 2307 1589 857 
1634 861 2172 2322 
2021 1381 2179 2077 
2126 1126 1547 345 
1477 1214 994 412 
831 978 1857 2085 
281 2406 1844 2174 
1779 2254 2334 521 
284 905...

result:

ok 

Test #58:

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

input:

2499 4 2499
1 2 2 3
1429 1 1 1429
3 4 4 7
1430 3 3 1430
5 6 6 1
1431 5 5 1431
7 8 8 11
1432 7 7 1432
9 10 10 5
1433 9 9 1433
11 12 12 15
1434 11 11 1434
13 14 14 9
1435 13 13 1435
15 16 16 19
1436 15 15 1436
17 18 18 13
1437 17 17 1437
19 20 20 23
1438 19 19 1438
21 22 22 17
1439 21 21 1439
23 24 24...

output:

3 2 1 2 
1 1429 1429 1 
7 4 3 4 
1430 3 1430 3 
6 1 5 6 
1431 5 1431 5 
11 8 7 8 
1432 7 1432 7 
5 10 9 10 
9 1433 1433 9 
15 12 11 12 
1434 11 1434 11 
14 9 13 14 
1435 13 1435 13 
19 16 15 16 
1436 15 1436 15 
13 18 17 18 
17 1437 1437 17 
23 20 19 20 
1438 19 1438 19 
22 17 21 22 
1439 21 1439 21...

result:

ok 

Test #59:

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

input:

5000 2 5000
3581 2773
462 1582
1171 208
74 4865
1018 10
1962 2532
578 1491
1140 4567
3640 4785
1051 3325
4545 2135
1152 286
309 4874
1953 3646
1794 234
1223 3529
3751 1002
3427 4740
4638 2554
933 1988
3177 1846
2440 2671
1315 3502
1382 2669
3145 443
438 2418
420 1154
671 3875
3152 1807
3618 1093
359...

output:

2773 3581 
462 1582 
1171 208 
4865 74 
10 1018 
2532 1962 
1491 578 
1140 4567 
4785 3640 
3325 1051 
2135 4545 
1152 286 
309 4874 
3646 1953 
234 1794 
3529 1223 
3751 1002 
4740 3427 
4638 2554 
933 1988 
3177 1846 
2671 2440 
1315 3502 
1382 2669 
443 3145 
438 2418 
420 1154 
3875 671 
3152 18...

result:

ok 

Test #60:

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

input:

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

output:

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

result:

ok 

Test #61:

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

input:

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

output:

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

result:

ok 

Test #62:

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

input:

156 64 156
29 104 122 93 114 102 62 151 145 125 155 109 97 116 62 72 83 122 60 109 125 19 14 101 80 125 76 155 123 128 123 57 7 154 36 60 123 36 19 89 12 3 29 36 145 66 9 13 132 26 97 89 4 95 92 19 86 140 33 89 55 5 102 119
148 71 119 10 75 47 27 30 4 109 92 63 55 28 2 156 3 123 84 10 60 13 5 93 125...

output:

119 140 5 13 55 4 145 66 33 92 19 89 122 76 155 123 132 36 102 80 95 125 109 60 57 29 97 62 19 123 14 89 9 86 101 3 104 19 114 89 26 93 12 36 116 128 125 123 29 155 97 145 72 109 154 60 83 7 151 62 122 102 36 125 
60 104 125 29 155 123 62 150 156 75 13 84 3 52 109 113 123 61 33 4 10 27 21 78 93 154 ...

result:

ok 

Test #63:

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

input:

9 1024 9
1 6 8 8 4 1 1 5 8 6 8 4 6 6 1 6 6 1 4 4 5 1 6 6 8 6 4 1 1 1 5 8 6 4 1 6 4 8 6 4 1 1 8 1 6 6 8 1 8 8 1 4 1 8 6 5 1 1 6 8 6 4 4 5 1 5 1 8 6 8 8 1 8 5 5 6 1 8 4 6 8 1 1 8 8 1 4 8 6 4 4 8 1 8 1 8 1 1 1 1 8 8 6 4 6 1 1 5 8 4 1 6 5 8 1 6 1 6 4 1 6 5 4 8 4 5 4 6 1 8 6 8 1 4 1 8 6 1 4 1 4 1 5 8 8 1...

output:

5 6 1 8 4 6 8 1 5 8 4 1 6 1 8 1 5 4 8 1 6 1 8 1 4 6 8 1 6 1 8 1 5 6 8 1 4 6 1 8 5 6 8 1 4 1 8 1 5 6 4 1 8 1 6 1 4 8 6 1 8 1 6 1 5 6 8 1 4 8 1 6 5 6 8 1 4 1 6 1 5 8 4 1 6 1 8 1 4 6 8 1 6 1 8 1 5 8 1 6 4 6 8 1 5 6 8 1 4 1 6 1 5 4 8 1 6 1 8 1 4 6 8 1 6 1 8 1 5 8 6 1 4 8 1 6 5 6 4 1 8 1 6 1 5 8 4 1 6 8 ...

result:

ok 

Test #64:

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

input:

2462 4 2401
595 1986 967 1326
19 173 880 2187
961 1645 843 1179
177 1102 1566 1225
1065 1553 961 354
1276 625 611 1814
1110 1097 572 845
780 2178 2041 1291
1531 415 1138 2390
1131 1649 499 584
752 1296 754 1982
2295 498 1627 1853
1647 1628 974 1282
265 2321 1271 2097
1161 123 2252 1776
439 723 487 4...

output:

1326 967 595 1986 
173 880 19 2187 
843 1179 1645 961 
1566 177 1225 1102 
1553 961 354 1065 
611 625 1276 1814 
845 1110 572 1097 
780 1291 2041 2178 
1138 2390 415 1531 
1131 584 499 1649 
752 754 1296 1982 
1853 2295 498 1627 
1282 1628 1647 974 
265 2097 1271 2321 
2252 1161 123 1776 
424 439 48...

result:

ok 

Test #65:

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

input:

4990 2 3
1 2
2 2
1 2
2 2
2 1
1 1
1 2
2 1
2 1
1 1
2 2
1 1
2 2
2 2
2 2
1 2
1 1
2 1
2 1
1 1
2 1
1 1
2 2
1 2
2 1
2 2
1 1
2 2
1 1
1 2
2 2
1 2
1 1
2 1
1 1
2 2
1 2
2 1
2 1
2 2
2 1
2 2
1 1
2 1
1 2
1 2
2 1
1 2
1 2
1 1
2 2
1 2
2 1
1 1
2 2
1 2
1 2
2 2
2 2
1 2
2 1
1 2
1 1
1 1
2 1
1 1
1 2
1 2
2 1
1 2
2 2
1 2
2 2...

output:

2 1 
2 2 
1 2 
2 2 
2 1 
1 1 
1 2 
2 1 
1 2 
1 1 
2 2 
1 1 
2 2 
2 2 
2 2 
2 1 
1 1 
1 2 
2 1 
1 1 
1 2 
1 1 
2 2 
2 1 
1 2 
2 2 
1 1 
2 2 
1 1 
2 1 
2 2 
1 2 
1 1 
2 1 
1 1 
2 2 
1 2 
2 1 
1 2 
2 2 
2 1 
2 2 
1 1 
1 2 
2 1 
1 2 
2 1 
1 2 
2 1 
1 1 
2 2 
1 2 
2 1 
1 1 
2 2 
1 2 
2 1 
2 2 
2 2 
1 2 
...

result:

ok 

Test #66:

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

input:

5000 2 5000
2970 2674
1208 2674
4977 2674
2674 3028
2674 36
1712 2674
3561 2674
2674 3033
4699 2674
2674 1785
2674 4345
2674 3302
2493 2674
2674 4280
2674 3999
4850 2674
2674 4508
3742 2674
2674 2718
2674 3461
260 2674
2674 4223
2069 2674
2674 1144
1975 2674
527 2674
2674 3260
2806 2674
3636 2674
26...

output:

2674 2970 
2674 1208 
2674 4977 
2674 3028 
2674 36 
2674 1712 
2674 3561 
2674 3033 
2674 4699 
2674 1785 
2674 4345 
2674 3302 
2674 2493 
2674 4280 
2674 3999 
2674 4850 
2674 4508 
2674 3742 
2674 2718 
2674 3461 
2674 260 
2674 4223 
2674 2069 
2674 1144 
2674 1975 
2674 527 
2674 3260 
2674 28...

result:

ok 

Test #67:

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

input:

2450 4 2401
317 417 657 793
1237 1460 1990 507
1030 1744 1155 1114
486 868 1284 2376
2391 704 1441 665
173 1283 789 1607
1309 1045 1466 2192
734 766 284 254
1814 1752 1181 937
1459 1638 1329 2346
1155 1205 443 1744
430 1096 1050 1098
930 2224 1622 186
1772 1916 1833 2196
2066 739 114 757
1180 786 99...

output:

793 417 657 317 
1460 1990 507 1237 
1114 1030 1744 1155 
486 1284 2376 868 
665 2391 1441 704 
173 1607 789 1283 
1466 2192 1045 1309 
766 284 254 734 
1181 1752 1814 937 
1329 1459 2346 1638 
1155 1744 443 1205 
430 1050 1096 1098 
1622 186 930 2224 
1916 2196 1772 1833 
757 114 2066 739 
996 277 ...

result:

ok 

Test #68:

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

input:

1250 8 1000
580 788 926 830 833 861 67 795
768 582 227 113 421 701 823 566
188 868 745 494 910 981 644 76
572 751 409 665 210 771 875 742
131 442 387 298 3 151 455 145
550 78 74 694 250 672 85 118
857 807 977 695 431 855 944 533
523 881 432 789 742 787 649 615
159 29 942 894 619 538 114 42
834 480 6...

output:

795 67 926 861 833 788 830 580 
823 566 421 582 768 113 701 227 
188 76 494 910 745 644 981 868 
742 771 875 572 210 751 665 409 
3 145 151 298 455 442 387 131 
118 74 694 672 78 85 550 250 
944 977 431 533 855 807 857 695 
649 615 789 742 787 523 881 432 
894 114 42 538 619 29 942 159 
28 614 602 2...

result:

ok 

Test #69:

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

input:

1248 8 1248
161 598 1246 131 374 981 761 969
119 257 749 837 658 163 674 826
564 891 1166 207 863 733 802 929
233 964 311 507 202 314 77 400
376 1093 71 445 709 408 1247 388
1020 581 966 19 468 403 48 566
1201 785 822 946 479 132 730 703
349 861 731 188 37 1202 18 183
882 126 896 333 614 1226 648 52...

output:

969 374 761 1246 598 981 161 131 
674 749 658 826 119 837 163 257 
733 207 802 564 891 863 929 1166 
77 400 507 311 964 202 233 314 
1093 408 445 388 376 709 1247 71 
1020 566 48 468 581 966 403 19 
703 132 822 946 479 730 1201 785 
18 37 731 183 861 188 349 1202 
648 614 1226 523 896 333 126 882 
9...

result:

ok 

Subtask #6:

score: 0
Runtime Error

Dependency #5:

100%
Accepted

Test #70:

score: 5
Accepted
time: 4ms
memory: 18220kb

input:

3 4 3
2 3 2 2
2 3 3 2
2 2 3 2

output:

3 2 2 2 
2 3 2 3 
2 2 3 2 

result:

ok 

Test #71:

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

input:

2450 4 2450
540 475 1156 2334
2421 2439 1328 750
471 1051 2007 1792
1776 786 705 2269
1277 755 1674 1622
590 1378 1217 603
967 239 1658 1920
857 2307 1589 78
2172 861 2322 1634
2077 2021 1381 2179
1126 345 1547 2126
994 1214 1477 412
1857 2085 831 978
281 1844 2406 2174
521 2334 2254 1779
1508 905 1...

output:

2334 475 1156 540 
750 2439 2421 1328 
2007 1051 1792 471 
786 2269 705 1776 
1277 1622 1674 755 
603 1217 1378 590 
1658 239 1920 967 
78 2307 1589 857 
1634 861 2172 2322 
2021 1381 2179 2077 
2126 1126 1547 345 
1477 1214 994 412 
831 978 1857 2085 
281 2406 1844 2174 
1779 2254 2334 521 
284 905...

result:

ok 

Test #72:

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

input:

2499 4 2499
1 2 2 3
1429 1 1 1429
3 4 4 7
1430 3 3 1430
5 6 6 1
1431 5 5 1431
7 8 8 11
1432 7 7 1432
9 10 10 5
1433 9 9 1433
11 12 12 15
1434 11 11 1434
13 14 14 9
1435 13 13 1435
15 16 16 19
1436 15 15 1436
17 18 18 13
1437 17 17 1437
19 20 20 23
1438 19 19 1438
21 22 22 17
1439 21 21 1439
23 24 24...

output:

3 2 1 2 
1 1429 1429 1 
7 4 3 4 
1430 3 1430 3 
6 1 5 6 
1431 5 1431 5 
11 8 7 8 
1432 7 1432 7 
5 10 9 10 
9 1433 1433 9 
15 12 11 12 
1434 11 1434 11 
14 9 13 14 
1435 13 1435 13 
19 16 15 16 
1436 15 1436 15 
13 18 17 18 
17 1437 1437 17 
23 20 19 20 
1438 19 1438 19 
22 17 21 22 
1439 21 1439 21...

result:

ok 

Test #73:

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

input:

5000 2 5000
3581 2773
462 1582
1171 208
74 4865
1018 10
1962 2532
578 1491
1140 4567
3640 4785
1051 3325
4545 2135
1152 286
309 4874
1953 3646
1794 234
1223 3529
3751 1002
3427 4740
4638 2554
933 1988
3177 1846
2440 2671
1315 3502
1382 2669
3145 443
438 2418
420 1154
671 3875
3152 1807
3618 1093
359...

output:

2773 3581 
462 1582 
1171 208 
4865 74 
10 1018 
2532 1962 
1491 578 
1140 4567 
4785 3640 
3325 1051 
2135 4545 
1152 286 
309 4874 
3646 1953 
234 1794 
3529 1223 
3751 1002 
4740 3427 
4638 2554 
933 1988 
3177 1846 
2671 2440 
1315 3502 
1382 2669 
443 3145 
438 2418 
420 1154 
3875 671 
3152 18...

result:

ok 

Test #74:

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

input:

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

output:

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

result:

ok 

Test #75:

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

input:

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

output:

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

result:

ok 

Test #76:

score: -5
Runtime Error

input:

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

output:


result:


Subtask #7:

score: 0
Skipped

Dependency #6:

0%

Subtask #8:

score: 20
Accepted

Dependency #2:

100%
Accepted

Dependency #5:

100%
Accepted

Test #117:

score: 20
Accepted
time: 96ms
memory: 77500kb

input:

100000 2 100000
70318 14894
32116 90327
63866 29061
53683 63612
70370 78264
42647 76881
39251 31741
61186 66491
57686 65819
53278 59145
71962 26052
81040 55279
50859 51310
46800 24546
85013 91165
61530 21890
84003 29099
33573 86182
49212 10639
91851 97312
57682 14067
5243 69674
99007 62508
26290 555...

output:

14894 70318 
32116 90327 
63866 29061 
53683 63612 
70370 78264 
76881 42647 
39251 31741 
61186 66491 
65819 57686 
59145 53278 
26052 71962 
81040 55279 
50859 51310 
24546 46800 
91165 85013 
61530 21890 
29099 84003 
33573 86182 
10639 49212 
97312 91851 
14067 57682 
5243 69674 
99007 62508 
55...

result:

ok 

Test #118:

score: 0
Accepted
time: 40ms
memory: 78172kb

input:

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

output:

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

result:

ok 

Test #119:

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

input:

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

output:

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

result:

ok 

Test #120:

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

input:

3 4 3
2 3 2 2
2 3 3 2
2 2 3 2

output:

3 2 2 2 
2 3 2 3 
2 2 3 2 

result:

ok 

Test #121:

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

input:

156 64 156
29 104 122 93 114 102 62 151 145 125 155 109 97 116 62 72 83 122 60 109 125 19 14 101 80 125 76 155 123 128 123 57 7 154 36 60 123 36 19 89 12 3 29 36 145 66 9 13 132 26 97 89 4 95 92 19 86 140 33 89 55 5 102 119
148 71 119 10 75 47 27 30 4 109 92 63 55 28 2 156 3 123 84 10 60 13 5 93 125...

output:

119 140 5 13 55 4 145 66 33 92 19 89 122 76 155 123 132 36 102 80 95 125 109 60 57 29 97 62 19 123 14 89 9 86 101 3 104 19 114 89 26 93 12 36 116 128 125 123 29 155 97 145 72 109 154 60 83 7 151 62 122 102 36 125 
60 104 125 29 155 123 62 150 156 75 13 84 3 52 109 113 123 61 33 4 10 27 21 78 93 154 ...

result:

ok 

Test #122:

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

input:

9 1024 9
1 6 8 8 4 1 1 5 8 6 8 4 6 6 1 6 6 1 4 4 5 1 6 6 8 6 4 1 1 1 5 8 6 4 1 6 4 8 6 4 1 1 8 1 6 6 8 1 8 8 1 4 1 8 6 5 1 1 6 8 6 4 4 5 1 5 1 8 6 8 8 1 8 5 5 6 1 8 4 6 8 1 1 8 8 1 4 8 6 4 4 8 1 8 1 8 1 1 1 1 8 8 6 4 6 1 1 5 8 4 1 6 5 8 1 6 1 6 4 1 6 5 4 8 4 5 4 6 1 8 6 8 1 4 1 8 6 1 4 1 4 1 5 8 8 1...

output:

5 6 1 8 4 6 8 1 5 8 4 1 6 1 8 1 5 4 8 1 6 1 8 1 4 6 8 1 6 1 8 1 5 6 8 1 4 6 1 8 5 6 8 1 4 1 8 1 5 6 4 1 8 1 6 1 4 8 6 1 8 1 6 1 5 6 8 1 4 8 1 6 5 6 8 1 4 1 6 1 5 8 4 1 6 1 8 1 4 6 8 1 6 1 8 1 5 8 1 6 4 6 8 1 5 6 8 1 4 1 6 1 5 4 8 1 6 1 8 1 4 6 8 1 6 1 8 1 5 8 6 1 4 8 1 6 5 6 4 1 8 1 6 1 5 8 4 1 6 8 ...

result:

ok 

Test #123:

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

input:

2462 4 2401
595 1986 967 1326
19 173 880 2187
961 1645 843 1179
177 1102 1566 1225
1065 1553 961 354
1276 625 611 1814
1110 1097 572 845
780 2178 2041 1291
1531 415 1138 2390
1131 1649 499 584
752 1296 754 1982
2295 498 1627 1853
1647 1628 974 1282
265 2321 1271 2097
1161 123 2252 1776
439 723 487 4...

output:

1326 967 595 1986 
173 880 19 2187 
843 1179 1645 961 
1566 177 1225 1102 
1553 961 354 1065 
611 625 1276 1814 
845 1110 572 1097 
780 1291 2041 2178 
1138 2390 415 1531 
1131 584 499 1649 
752 754 1296 1982 
1853 2295 498 1627 
1282 1628 1647 974 
265 2097 1271 2321 
2252 1161 123 1776 
424 439 48...

result:

ok 

Test #124:

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

input:

4990 2 3
1 2
2 2
1 2
2 2
2 1
1 1
1 2
2 1
2 1
1 1
2 2
1 1
2 2
2 2
2 2
1 2
1 1
2 1
2 1
1 1
2 1
1 1
2 2
1 2
2 1
2 2
1 1
2 2
1 1
1 2
2 2
1 2
1 1
2 1
1 1
2 2
1 2
2 1
2 1
2 2
2 1
2 2
1 1
2 1
1 2
1 2
2 1
1 2
1 2
1 1
2 2
1 2
2 1
1 1
2 2
1 2
1 2
2 2
2 2
1 2
2 1
1 2
1 1
1 1
2 1
1 1
1 2
1 2
2 1
1 2
2 2
1 2
2 2...

output:

2 1 
2 2 
1 2 
2 2 
2 1 
1 1 
1 2 
2 1 
1 2 
1 1 
2 2 
1 1 
2 2 
2 2 
2 2 
2 1 
1 1 
1 2 
2 1 
1 1 
1 2 
1 1 
2 2 
2 1 
1 2 
2 2 
1 1 
2 2 
1 1 
2 1 
2 2 
1 2 
1 1 
2 1 
1 1 
2 2 
1 2 
2 1 
1 2 
2 2 
2 1 
2 2 
1 1 
1 2 
2 1 
1 2 
2 1 
1 2 
2 1 
1 1 
2 2 
1 2 
2 1 
1 1 
2 2 
1 2 
2 1 
2 2 
2 2 
1 2 
...

result:

ok 

Test #125:

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

input:

5000 2 5000
2970 2674
1208 2674
4977 2674
2674 3028
2674 36
1712 2674
3561 2674
2674 3033
4699 2674
2674 1785
2674 4345
2674 3302
2493 2674
2674 4280
2674 3999
4850 2674
2674 4508
3742 2674
2674 2718
2674 3461
260 2674
2674 4223
2069 2674
2674 1144
1975 2674
527 2674
2674 3260
2806 2674
3636 2674
26...

output:

2674 2970 
2674 1208 
2674 4977 
2674 3028 
2674 36 
2674 1712 
2674 3561 
2674 3033 
2674 4699 
2674 1785 
2674 4345 
2674 3302 
2674 2493 
2674 4280 
2674 3999 
2674 4850 
2674 4508 
2674 3742 
2674 2718 
2674 3461 
2674 260 
2674 4223 
2674 2069 
2674 1144 
2674 1975 
2674 527 
2674 3260 
2674 28...

result:

ok 

Test #126:

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

input:

2450 4 2401
317 417 657 793
1237 1460 1990 507
1030 1744 1155 1114
486 868 1284 2376
2391 704 1441 665
173 1283 789 1607
1309 1045 1466 2192
734 766 284 254
1814 1752 1181 937
1459 1638 1329 2346
1155 1205 443 1744
430 1096 1050 1098
930 2224 1622 186
1772 1916 1833 2196
2066 739 114 757
1180 786 99...

output:

793 417 657 317 
1460 1990 507 1237 
1114 1030 1744 1155 
486 1284 2376 868 
665 2391 1441 704 
173 1607 789 1283 
1466 2192 1045 1309 
766 284 254 734 
1181 1752 1814 937 
1329 1459 2346 1638 
1155 1744 443 1205 
430 1050 1096 1098 
1622 186 930 2224 
1916 2196 1772 1833 
757 114 2066 739 
996 277 ...

result:

ok 

Test #127:

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

input:

1250 8 1000
580 788 926 830 833 861 67 795
768 582 227 113 421 701 823 566
188 868 745 494 910 981 644 76
572 751 409 665 210 771 875 742
131 442 387 298 3 151 455 145
550 78 74 694 250 672 85 118
857 807 977 695 431 855 944 533
523 881 432 789 742 787 649 615
159 29 942 894 619 538 114 42
834 480 6...

output:

795 67 926 861 833 788 830 580 
823 566 421 582 768 113 701 227 
188 76 494 910 745 644 981 868 
742 771 875 572 210 751 665 409 
3 145 151 298 455 442 387 131 
118 74 694 672 78 85 550 250 
944 977 431 533 855 807 857 695 
649 615 789 742 787 523 881 432 
894 114 42 538 619 29 942 159 
28 614 602 2...

result:

ok 

Test #128:

score: 0
Accepted
time: 86ms
memory: 71700kb

input:

98045 2 95001
27085 59126
75021 23663
67175 78883
3919 90698
20718 67504
49374 44011
1660 3236
71971 79270
24502 90540
54202 9732
14395 88659
56600 52635
21912 17986
92420 56526
40254 3472
64330 20431
9381 56003
57750 45529
45230 9388
83797 53437
75562 47526
63126 45219
71020 87437
50298 2016
21982 ...

output:

59126 27085 
23663 75021 
78883 67175 
3919 90698 
20718 67504 
44011 49374 
3236 1660 
79270 71971 
90540 24502 
9732 54202 
14395 88659 
56600 52635 
17986 21912 
92420 56526 
3472 40254 
20431 64330 
56003 9381 
45529 57750 
9388 45230 
53437 83797 
47526 75562 
63126 45219 
71020 87437 
2016 502...

result:

ok 

Test #129:

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

input:

1248 8 1248
161 598 1246 131 374 981 761 969
119 257 749 837 658 163 674 826
564 891 1166 207 863 733 802 929
233 964 311 507 202 314 77 400
376 1093 71 445 709 408 1247 388
1020 581 966 19 468 403 48 566
1201 785 822 946 479 132 730 703
349 861 731 188 37 1202 18 183
882 126 896 333 614 1226 648 52...

output:

969 374 761 1246 598 981 161 131 
674 749 658 826 119 837 163 257 
733 207 802 564 891 863 929 1166 
77 400 507 311 964 202 233 314 
1093 408 445 388 376 709 1247 71 
1020 566 48 468 581 966 403 19 
703 132 822 946 479 730 1201 785 
18 37 731 183 861 188 349 1202 
648 614 1226 523 896 333 126 882 
9...

result:

ok 

Test #130:

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

input:

2450 4 2450
540 475 1156 2334
2421 2439 1328 750
471 1051 2007 1792
1776 786 705 2269
1277 755 1674 1622
590 1378 1217 603
967 239 1658 1920
857 2307 1589 78
2172 861 2322 1634
2077 2021 1381 2179
1126 345 1547 2126
994 1214 1477 412
1857 2085 831 978
281 1844 2406 2174
521 2334 2254 1779
1508 905 1...

output:

2334 475 1156 540 
750 2439 2421 1328 
2007 1051 1792 471 
786 2269 705 1776 
1277 1622 1674 755 
603 1217 1378 590 
1658 239 1920 967 
78 2307 1589 857 
1634 861 2172 2322 
2021 1381 2179 2077 
2126 1126 1547 345 
1477 1214 994 412 
831 978 1857 2085 
281 2406 1844 2174 
1779 2254 2334 521 
284 905...

result:

ok 

Test #131:

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

input:

2499 4 2499
1 2 2 3
1429 1 1 1429
3 4 4 7
1430 3 3 1430
5 6 6 1
1431 5 5 1431
7 8 8 11
1432 7 7 1432
9 10 10 5
1433 9 9 1433
11 12 12 15
1434 11 11 1434
13 14 14 9
1435 13 13 1435
15 16 16 19
1436 15 15 1436
17 18 18 13
1437 17 17 1437
19 20 20 23
1438 19 19 1438
21 22 22 17
1439 21 21 1439
23 24 24...

output:

3 2 1 2 
1 1429 1429 1 
7 4 3 4 
1430 3 1430 3 
6 1 5 6 
1431 5 1431 5 
11 8 7 8 
1432 7 1432 7 
5 10 9 10 
9 1433 1433 9 
15 12 11 12 
1434 11 1434 11 
14 9 13 14 
1435 13 1435 13 
19 16 15 16 
1436 15 1436 15 
13 18 17 18 
17 1437 1437 17 
23 20 19 20 
1438 19 1438 19 
22 17 21 22 
1439 21 1439 21...

result:

ok 

Test #132:

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

input:

5000 2 5000
3581 2773
462 1582
1171 208
74 4865
1018 10
1962 2532
578 1491
1140 4567
3640 4785
1051 3325
4545 2135
1152 286
309 4874
1953 3646
1794 234
1223 3529
3751 1002
3427 4740
4638 2554
933 1988
3177 1846
2440 2671
1315 3502
1382 2669
3145 443
438 2418
420 1154
671 3875
3152 1807
3618 1093
359...

output:

2773 3581 
462 1582 
1171 208 
4865 74 
10 1018 
2532 1962 
1491 578 
1140 4567 
4785 3640 
3325 1051 
2135 4545 
1152 286 
309 4874 
3646 1953 
234 1794 
3529 1223 
3751 1002 
4740 3427 
4638 2554 
933 1988 
3177 1846 
2671 2440 
1315 3502 
1382 2669 
443 3145 
438 2418 
420 1154 
3875 671 
3152 18...

result:

ok 

Test #133:

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

input:

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

output:

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

result:

ok 

Test #134:

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

input:

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

output:

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

result:

ok 

Test #135:

score: 0
Accepted
time: 562ms
memory: 112848kb

input:

62400 8 62400
617 61873 50005 41067 20321 15682 32071 28672
22133 8305 52336 45992 33172 47471 17329 39927
42134 45570 15289 42551 55858 19194 10715 10649
8176 5735 13244 20965 61861 7073 12818 5527
21000 8783 29108 17636 58752 9701 42134 11867
35793 5665 25545 53912 41719 7606 30422 4734
6540 43594...

output:

28672 15682 32071 50005 61873 20321 41067 617 
17329 52336 45992 39927 22133 33172 47471 8305 
10715 55858 10649 19194 15289 45570 42134 42551 
5527 12818 61861 20965 8176 5735 7073 13244 
42134 9701 11867 21000 17636 29108 58752 8783 
7606 53912 41719 4734 5665 25545 30422 35793 
8033 34106 7781 49...

result:

ok 

Test #136:

score: 0
Accepted
time: 336ms
memory: 39252kb

input:

488 1024 488
437 386 352 3 204 235 111 327 270 195 436 108 324 319 398 484 177 270 133 272 484 202 67 380 1 215 36 327 104 412 432 67 157 455 286 196 62 262 437 4 289 108 272 402 136 265 291 48 135 182 385 319 112 186 70 50 273 196 231 195 17 319 178 270 132 424 78 406 324 346 57 71 97 186 396 422 3...

output:

356 147 404 464 95 7 137 442 354 229 311 44 473 223 166 254 9 340 351 4 41 158 314 388 445 228 74 68 99 367 327 62 400 97 86 366 394 25 424 48 143 130 200 274 107 347 59 156 88 439 91 303 121 56 482 448 194 416 365 290 131 184 72 357 297 179 221 155 54 402 301 205 462 450 258 484 403 441 295 272 275...

result:

ok 

Test #137:

score: 0
Accepted
time: 28ms
memory: 19408kb

input:

6 16384 6
2 5 1 6 5 2 5 1 6 1 5 5 6 5 5 6 2 6 2 1 6 6 5 5 6 5 2 2 1 1 1 6 5 1 5 6 6 2 6 1 2 6 6 2 2 1 6 6 6 1 5 5 1 5 5 6 2 5 1 5 1 5 1 2 5 1 1 6 5 6 5 2 1 1 6 1 6 6 5 5 5 1 5 6 2 5 6 5 5 6 6 6 2 5 5 6 2 5 6 1 5 6 6 2 2 5 1 2 5 5 6 5 6 6 1 1 2 2 5 5 6 5 6 5 5 1 6 6 6 6 1 6 5 6 5 2 6 6 6 5 5 6 6 6 6 ...

output:

2 1 6 5 2 1 6 5 2 1 6 5 6 5 6 5 2 1 6 5 2 1 6 5 2 1 6 5 6 5 6 5 2 1 6 5 2 1 6 5 2 1 6 5 6 5 6 5 2 1 6 5 6 5 6 5 2 1 6 5 6 5 6 5 2 1 6 5 2 1 6 5 2 1 6 5 6 5 6 5 2 1 6 5 1 6 5 6 2 1 6 5 6 5 6 5 2 1 6 5 2 1 6 5 2 1 6 5 6 5 6 5 2 1 6 5 6 5 6 5 2 1 6 5 6 5 6 5 2 1 6 5 2 1 6 5 2 1 5 6 5 6 5 6 2 1 5 6 1 5 ...

result:

ok 

Test #138:

score: 0
Accepted
time: 98ms
memory: 36796kb

input:

6035 32 3126
2384 1507 1419 2790 466 3034 613 391 1142 1913 2728 1770 1249 2719 457 1720 2670 541 568 1711 1147 1498 2929 1920 2067 351 2089 1076 3001 2562 2615 1630
1719 1848 849 3098 1026 1016 2612 2228 526 2395 1808 1898 1626 2249 2857 1473 2360 2448 1450 1045 55 2166 2597 1586 1181 540 789 612 1...

output:

1630 2615 2562 2089 1076 3001 1147 2929 1920 2670 2067 1249 541 2719 568 466 2384 2728 1711 457 351 1498 1507 391 2790 1142 613 1913 1720 3034 1419 1770 
1579 2828 789 335 1181 2448 841 55 540 1450 2612 2360 2166 612 1626 1586 526 2395 849 2597 1473 1808 1719 2249 2228 3098 1045 1026 1016 1848 2857 ...

result:

ok 

Test #139:

score: 0
Accepted
time: 80ms
memory: 67832kb

input:

89868 2 20001
16598 13223
18759 19981
2642 8681
4102 18080
11473 16749
690 15290
17900 16229
10684 17481
6328 12171
9417 1150
7185 5689
10346 17102
17958 9727
2117 13756
10955 13157
245 2840
5257 5337
16622 6429
17516 10772
13007 19349
11359 2821
14341 8897
3974 2482
16241 17966
18146 15458
3345 158...

output:

13223 16598 
19981 18759 
2642 8681 
18080 4102 
11473 16749 
15290 690 
16229 17900 
17481 10684 
6328 12171 
9417 1150 
5689 7185 
17102 10346 
9727 17958 
2117 13756 
13157 10955 
245 2840 
5337 5257 
6429 16622 
10772 17516 
19349 13007 
11359 2821 
8897 14341 
3974 2482 
17966 16241 
15458 1814...

result:

ok 

Test #140:

score: 0
Accepted
time: 241ms
memory: 35176kb

input:

442 1024 442
204 189 272 54 225 232 246 111 211 39 140 31 133 213 40 172 5 229 225 147 176 81 31 108 40 148 128 210 21 262 105 163 228 247 259 161 184 211 3 211 261 277 70 186 27 195 89 282 233 258 169 215 154 267 21 239 264 213 91 131 295 39 163 282 254 63 286 282 9 116 139 285 76 206 85 233 73 180...

output:

64 216 160 98 278 185 191 122 157 2 68 65 46 178 214 60 296 231 142 215 201 71 14 288 118 109 161 77 250 253 299 150 287 234 125 247 180 120 221 110 12 158 195 193 291 249 37 269 251 284 25 26 32 56 264 263 100 72 237 199 169 183 138 285 61 176 22 170 294 197 81 175 94 4 203 8 44 11 152 200 30 194 1...

result:

ok 

Test #141:

score: 0
Accepted
time: 448ms
memory: 93764kb

input:

59767 8 50000
14021 37442 6924 2683 26908 28108 49331 4157
37602 8443 19287 12234 4215 29554 33860 1201
2453 34206 48003 47930 30310 48979 24906 2040
19079 30112 42351 26155 23394 37361 37618 35224
18576 29106 48671 22449 25578 19435 4011 7931
7174 13442 3382 24117 23309 31964 19031 45122
33083 3854...

output:

4157 28108 2683 26908 49331 37442 6924 14021 
8443 1201 33860 19287 12234 29554 37602 4215 
30310 2040 48979 2453 34206 24906 48003 47930 
35224 26155 19079 23394 30112 37361 42351 37618 
19435 4011 7931 18576 29106 22449 48671 25578 
24117 19031 45122 3382 31964 23309 13442 7174 
22862 45872 5388 4...

result:

ok 

Test #142:

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

input:

62500 8 62500
51504 53517 18444 47810 55743 52115 39033 39945
39582 40153 48723 405 57762 57932 38589 34957
46544 29639 46926 5502 36080 4497 12837 5415
40364 54270 15841 56968 20512 49512 23271 29535
32613 29997 43963 8109 43144 40423 38621 31273
32431 16718 11192 30443 19278 38857 30834 60796
1958...

output:

39945 47810 39033 18444 55743 53517 52115 51504 
38589 57932 405 57762 48723 34957 39582 40153 
5502 12837 36080 46544 4497 29639 5415 46926 
20512 29535 23271 56968 40364 49512 15841 54270 
43963 38621 40423 31273 43144 32613 29997 8109 
30443 30834 60796 19278 38857 32431 11192 16718 
48478 19582 ...

result:

ok 

Test #143:

score: 0
Accepted
time: 142ms
memory: 26296kb

input:

61 8192 61
47 47 47 47 47 36 36 47 36 36 36 47 36 47 36 47 47 36 36 36 47 36 36 36 47 36 47 47 47 36 47 36 36 47 47 36 47 47 47 47 47 47 36 36 36 47 47 21 36 36 36 36 47 47 36 47 36 47 47 47 36 47 47 47 47 36 36 47 36 47 36 47 47 36 47 47 36 47 47 36 36 36 36 36 47 36 36 36 36 47 36 47 36 47 47 36 3...

output:

3 51 36 47 36 47 36 47 36 47 36 47 36 47 36 47 36 47 36 47 36 47 36 47 36 47 36 47 36 47 36 47 10 30 36 47 36 47 36 47 47 36 47 36 47 36 47 36 36 47 36 47 36 47 36 47 36 47 36 47 36 47 36 47 48 36 47 36 47 36 47 36 47 36 47 36 47 36 47 36 60 47 36 47 36 47 36 47 36 47 36 47 36 47 36 47 13 47 15 36 3...

result:

ok 

Test #144:

score: 0
Accepted
time: 118ms
memory: 24264kb

input:

50 8192 50
40 29 20 40 40 40 20 40 40 40 40 49 20 20 40 40 20 40 40 20 20 20 40 20 40 40 20 20 40 40 40 40 40 20 40 40 40 40 40 40 20 40 20 40 20 40 40 20 40 40 20 20 40 20 40 40 20 40 40 40 20 19 40 40 40 40 20 40 20 40 20 20 20 20 20 20 20 40 20 40 20 20 20 40 40 40 40 40 40 40 20 20 40 20 20 40 4...

output:

36 40 20 40 20 40 20 40 20 40 20 40 20 40 20 40 22 20 40 20 40 20 40 20 40 20 40 20 40 20 40 20 41 21 20 40 20 40 20 40 40 20 40 20 40 20 40 20 20 40 20 40 20 40 20 40 20 40 20 40 20 40 20 40 28 18 40 20 40 20 40 20 40 20 40 20 40 20 40 20 40 20 40 20 40 20 40 20 40 20 40 20 40 20 40 20 16 20 40 20 ...

result:

ok 

Test #145:

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

input:

56000 8 50000
38540 29053 29109 38746 29288 38450 43383 32332
14057 662 19282 8910 49216 18920 32722 25913
4461 24280 3328 17870 569 37854 3246 27991
35958 21836 18035 12840 25641 36792 21982 33634
6456 49901 35635 42812 24541 44145 8939 11926
29442 26462 18739 27152 42797 5777 15117 19193
40156 501...

output:

32332 38450 29288 29053 43383 29109 38746 38540 
8910 25913 32722 14057 18920 662 19282 49216 
3328 3246 37854 569 27991 17870 4461 24280 
33634 21982 21836 36792 18035 35958 25641 12840 
44145 8939 24541 11926 6456 42812 35635 49901 
19193 15117 5777 42797 18739 26462 29442 27152 
34145 45047 20160...

result:

ok 

Test #146:

score: 0
Accepted
time: 457ms
memory: 73212kb

input:

61952 8 61952
31143 31143 3756 34556 4617 49727 3756 48229
48054 10150 10150 1113 46750 1113 11148 44687
18150 50774 34447 50642 31286 44185 50642 18150
18803 8000 20838 21039 20764 18803 20764 56246
59196 9154 49057 7963 47927 59196 59996 7963
27925 33037 27925 25590 4557 12519 33037 21779
9336 551...

output:

48229 3756 49727 31143 4617 34556 3756 31143 
44687 1113 46750 10150 11148 1113 10150 48054 
44185 50642 18150 31286 34447 50774 18150 50642 
56246 18803 20838 20764 8000 21039 20764 18803 
49057 59996 59196 7963 47927 9154 59196 7963 
4557 27925 21779 33037 12519 25590 33037 27925 
1848 1425 56435 ...

result:

ok 

Test #147:

score: 0
Accepted
time: 103ms
memory: 81008kb

input:

99995 4 99995
1 2 28571 28571
2 4 28572 28572
3 1 28573 28573
4 6 28574 28574
5 3 28575 28575
6 8 28576 28576
7 5 28577 28577
8 10 28578 28578
9 7 28579 28579
10 12 28580 28580
11 9 28581 28581
12 14 28582 28582
13 11 28583 28583
14 16 28584 28584
15 13 28585 28585
16 18 28586 28586
17 15 28587 2858...

output:

2 28571 1 28571 
4 28572 2 28572 
28573 1 3 28573 
6 28574 4 28574 
3 28575 5 28575 
8 28576 6 28576 
28577 5 7 28577 
10 28578 8 28578 
7 28579 9 28579 
12 28580 10 28580 
28581 9 11 28581 
14 28582 12 28582 
11 28583 13 28583 
16 28584 14 28584 
28585 13 15 28585 
18 28586 16 28586 
15 28587 17 28...

result:

ok 

Test #148:

score: 0
Accepted
time: 119ms
memory: 80080kb

input:

99995 4 99995
1 2 2 3
57141 1 1 57141
3 4 4 7
57142 3 3 57142
5 6 6 1
57143 5 5 57143
7 8 8 11
57144 7 7 57144
9 10 10 5
57145 9 9 57145
11 12 12 15
57146 11 11 57146
13 14 14 9
57147 13 13 57147
15 16 16 19
57148 15 15 57148
17 18 18 13
57149 17 17 57149
19 20 20 23
57150 19 19 57150
21 22 22 17
57...

output:

3 2 1 2 
1 57141 57141 1 
7 4 3 4 
57142 3 57142 3 
6 1 5 6 
57143 5 57143 5 
11 8 7 8 
57144 7 57144 7 
5 10 9 10 
9 57145 57145 9 
15 12 11 12 
57146 11 57146 11 
14 9 13 14 
57147 13 57147 13 
19 16 15 16 
57148 15 57148 15 
13 18 17 18 
17 57149 57149 17 
23 20 19 20 
57150 19 57150 19 
22 17 21...

result:

ok 

Test #149:

score: 0
Accepted
time: 123ms
memory: 84408kb

input:

99995 4 99995
71425 71425 99994 99995
71424 71424 99992 99994
71423 71423 99995 99993
71422 71422 99990 99992
71421 71421 99993 99991
71420 71420 99988 99990
71419 71419 99991 99989
71418 71418 99986 99988
71417 71417 99989 99987
71416 71416 99984 99986
71415 71415 99987 99985
71414 71414 99982 9998...

output:

99995 71425 99994 71425 
99994 71424 99992 71424 
99993 71423 71423 99995 
99992 71422 99990 71422 
99991 71421 99993 71421 
99990 71420 99988 71420 
99989 71419 71419 99991 
99988 71418 99986 71418 
99987 71417 99989 71417 
99986 71416 99984 71416 
99985 71415 71415 99987 
99984 71414 99982 71414 
...

result:

ok 

Test #150:

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

input:

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

output:

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

result:

ok 

Test #151:

score: 0
Accepted
time: 103ms
memory: 84304kb

input:

99995 4 99995
99993 99994 99994 99995
42855 99995 99995 42855
99989 99992 99992 99993
42854 99993 99993 42854
99995 99990 99990 99991
42853 99991 99991 42853
99985 99988 99988 99989
42852 99989 99989 42852
99991 99986 99986 99987
42851 99987 99987 42851
99981 99984 99984 99985
42850 99985 99985 4285...

output:

99995 99994 99993 99994 
42855 99995 99995 42855 
99993 99992 99989 99992 
42854 99993 42854 99993 
99991 99990 99990 99995 
42853 99991 42853 99991 
99989 99988 99985 99988 
42852 99989 42852 99989 
99987 99986 99991 99986 
42851 99987 99987 42851 
99985 99984 99981 99984 
42850 99985 42850 99985 
...

result:

ok 

Test #152:

score: 0
Accepted
time: 107ms
memory: 81220kb

input:

99995 4 99995
71425 71425 85710 85710
71424 71424 85709 85709
71423 71423 85708 85708
71422 71422 85707 85707
71421 71421 85706 85706
71420 71420 85705 85705
71419 71419 85704 85704
71418 71418 85703 85703
71417 71417 85702 85702
71416 71416 85701 85701
71415 71415 85700 85700
71414 71414 85699 8569...

output:

85710 71425 85710 71425 
71424 85709 85709 71424 
71423 85708 85708 71423 
71422 85707 85707 71422 
85706 71421 85706 71421 
71420 85705 85705 71420 
71419 85704 85704 71419 
71418 85703 85703 71418 
85702 71417 85702 71417 
71416 85701 85701 71416 
71415 85700 85700 71415 
71414 85699 85699 71414 
...

result:

ok 

Test #153:

score: 0
Accepted
time: 105ms
memory: 80008kb

input:

99995 4 99995
71425 71425 85710 85710
71424 71424 85709 85709
71423 71423 85708 85708
71422 71422 85707 85707
71421 71421 85706 85706
71420 71420 85705 85705
71419 71419 85704 85704
71418 71418 85703 85703
71417 71417 85702 85702
71416 71416 85701 85701
71415 71415 85700 85700
71414 71414 85699 8569...

output:

85710 71425 85710 71425 
71424 85709 85709 71424 
71423 85708 85708 71423 
71422 85707 85707 71422 
85706 71421 85706 71421 
71420 85705 85705 71420 
71419 85704 85704 71419 
71418 85703 85703 71418 
85702 71417 85702 71417 
71416 85701 85701 71416 
71415 85700 85700 71415 
71414 85699 85699 71414 
...

result:

ok 

Test #154:

score: 0
Accepted
time: 110ms
memory: 80196kb

input:

99995 4 99995
14286 14286 28571 28571
14287 14287 28572 28572
14288 14288 28573 28573
14289 14289 28574 28574
14290 14290 28575 28575
14291 14291 28576 28576
14292 14292 28577 28577
14293 14293 28578 28578
14294 14294 28579 28579
14295 14295 28580 28580
14296 14296 28581 28581
14297 14297 28582 2858...

output:

28571 14286 28571 14286 
28572 14287 14287 28572 
28573 14288 14288 28573 
28574 14289 14289 28574 
28575 14290 28575 14290 
28576 14291 14291 28576 
28577 14292 14292 28577 
28578 14293 14293 28578 
28579 14294 28579 14294 
28580 14295 14295 28580 
28581 14296 14296 28581 
28582 14297 14297 28582 
...

result:

ok 

Test #155:

score: 0
Accepted
time: 107ms
memory: 79900kb

input:

99995 4 99995
14286 14286 28571 28571
14287 14287 28572 28572
14288 14288 28573 28573
14289 14289 28574 28574
14290 14290 28575 28575
14291 14291 28576 28576
14292 14292 28577 28577
14293 14293 28578 28578
14294 14294 28579 28579
14295 14295 28580 28580
14296 14296 28581 28581
14297 14297 28582 2858...

output:

28571 14286 28571 14286 
28572 14287 14287 28572 
28573 14288 14288 28573 
28574 14289 14289 28574 
28575 14290 28575 14290 
28576 14291 14291 28576 
28577 14292 14292 28577 
28578 14293 14293 28578 
28579 14294 28579 14294 
28580 14295 14295 28580 
28581 14296 14296 28581 
28582 14297 14297 28582 
...

result:

ok 

Test #156:

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

input:

62496 8 62496
1 1 2 2 17857 17857 17857 17857
2 2 4 4 17858 17858 17858 17858
3 3 1 1 17859 17859 17859 17859
4 4 6 6 17860 17860 17860 17860
5 5 3 3 17861 17861 17861 17861
6 6 8 8 17862 17862 17862 17862
7 7 5 5 17863 17863 17863 17863
8 8 10 10 17864 17864 17864 17864
9 9 7 7 17865 17865 17865 17...

output:

2 17857 1 17857 2 17857 1 17857 
4 17858 2 17858 4 17858 2 17858 
1 17859 3 17859 1 17859 3 17859 
6 17860 4 17860 6 17860 4 17860 
3 17861 5 17861 3 17861 5 17861 
8 17862 6 17862 8 17862 6 17862 
5 17863 7 17863 5 17863 7 17863 
10 17864 8 17864 10 17864 8 17864 
7 17865 9 17865 7 17865 9 17865 
1...

result:

ok 

Test #157:

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

input:

62496 8 62496
1 3 2 2 2 2 1 3
35713 35713 1 1 1 1 35713 35713
3 7 4 4 4 4 3 7
35714 35714 3 3 3 3 35714 35714
5 1 6 6 6 6 5 1
35715 35715 5 5 5 5 35715 35715
7 11 8 8 8 8 7 11
35716 35716 7 7 7 7 35716 35716
9 5 10 10 10 10 9 5
35717 35717 9 9 9 9 35717 35717
11 15 12 12 12 12 11 15
35718 35718 11 1...

output:

3 2 1 2 3 2 1 2 
35713 1 35713 1 35713 1 35713 1 
7 4 3 4 7 4 3 4 
35714 3 35714 3 35714 3 35714 3 
1 6 5 6 1 6 5 6 
35715 5 35715 5 35715 5 35715 5 
11 8 7 8 11 8 7 8 
35716 7 35716 7 35716 7 35716 7 
5 10 9 10 5 10 9 10 
35717 9 35717 9 35717 9 35717 9 
15 12 11 12 15 12 11 12 
35718 11 35718 11 3...

result:

ok 

Test #158:

score: 0
Accepted
time: 81ms
memory: 71584kb

input:

100000 2 100000
53479 25002
53479 63606
53479 40735
53479 83340
53479 40775
53479 11458
53479 8684
53479 60405
45116 53479
67722 53479
26014 53479
87860 53479
55147 53479
53479 22726
53479 67769
53479 129
14600 53479
53479 21514
53479 32164
60088 53479
53479 25415
70946 53479
53479 27091
33386 53479...

output:

25002 53479 
53479 63606 
53479 40735 
53479 83340 
53479 40775 
53479 11458 
53479 8684 
53479 60405 
53479 45116 
53479 67722 
53479 26014 
53479 87860 
53479 55147 
53479 22726 
53479 67769 
53479 129 
53479 14600 
53479 21514 
53479 32164 
53479 60088 
53479 25415 
53479 70946 
53479 27091 
5347...

result:

ok 

Test #159:

score: 0
Accepted
time: 87ms
memory: 79136kb

input:

100000 2 90000
8483 66963
63660 79073
41795 20397
1296 84311
3690 21178
21052 31611
51423 14323
34208 82468
83835 2785
50594 28274
59957 10993
34259 64334
89407 73934
14947 61083
53201 89472
61243 33351
76632 58718
67464 85318
54224 45096
84552 76529
44253 30697
43669 3108
26489 64691
79840 85776
76...

output:

66963 8483 
63660 79073 
41795 20397 
84311 1296 
3690 21178 
21052 31611 
51423 14323 
34208 82468 
2785 83835 
50594 28274 
59957 10993 
34259 64334 
73934 89407 
14947 61083 
53201 89472 
33351 61243 
58718 76632 
85318 67464 
45096 54224 
84552 76529 
30697 44253 
43669 3108 
64691 26489 
79840 ...

result:

ok 

Test #160:

score: 0
Accepted
time: 96ms
memory: 59504kb

input:

99458 2 99458
80944 83824
25208 26621
57146 28836
43915 18169
59242 47842
34224 78881
38791 20722
89723 91046
72800 40306
92681 94906
41151 7263
76035 13332
93928 38800
97168 86055
44186 73623
68071 7391
20692 72265
44111 42596
36037 77687
64592 836
43568 35187
34861 88539
37477 22111
85787 98028
73...

output:

83824 80944 
26621 25208 
28836 57146 
18169 43915 
47842 59242 
78881 34224 
20722 38791 
91046 89723 
40306 72800 
94906 92681 
7263 41151 
13332 76035 
38800 93928 
86055 97168 
73623 44186 
7391 68071 
72265 20692 
42596 44111 
77687 36037 
836 64592 
35187 43568 
88539 34861 
22111 37477 
98028...

result:

ok 

Test #161:

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

input:

100000 2 100000
91980 92592
12359 10704
35873 56718
28601 20301
78422 55548
74736 59974
81664 29025
55916 70432
47381 34185
31764 56168
33997 30947
70076 9029
52532 67057
79680 99273
54410 56704
45238 71652
12615 6894
66478 78041
40520 5451
58133 5950
89237 70551
36028 97551
83553 90630
15211 33690
...

output:

92592 91980 
12359 10704 
35873 56718 
28601 20301 
55548 78422 
74736 59974 
29025 81664 
70432 55916 
47381 34185 
56168 31764 
33997 30947 
70076 9029 
67057 52532 
99273 79680 
56704 54410 
45238 71652 
6894 12615 
66478 78041 
5451 40520 
5950 58133 
70551 89237 
97551 36028 
90630 83553 
33690...

result:

ok 

Test #162:

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

input:

99555 2 99555
79301 40457
40457 80634
49074 21580
92701 14354
44540 70461
47132 47637
84954 27979
87556 60683
22633 43063
49914 63643
4494 3571
88758 53632
17055 50019
49334 79039
67659 50111
17945 48061
84596 60323
14629 72033
77184 30069
64209 36217
49947 35279
45866 44707
58146 58484
1393 53385
4...

output:

40457 79301 
80634 40457 
21580 49074 
14354 92701 
70461 44540 
47637 47132 
27979 84954 
60683 87556 
22633 43063 
49914 63643 
3571 4494 
88758 53632 
50019 17055 
79039 49334 
50111 67659 
48061 17945 
84596 60323 
14629 72033 
30069 77184 
36217 64209 
35279 49947 
45866 44707 
58146 58484 
533...

result:

ok 

Subtask #9:

score: 0
Skipped

Dependency #3:

100%
Accepted

Dependency #6:

0%

Subtask #10:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Dependency #6:

0%