QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#527320#7278. Brought Down the Grading Server?skittles141250 159ms37812kbC++173.8kb2024-08-22 13:59:242024-08-22 13:59:24

Judging History

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

  • [2024-08-22 13:59:24]
  • 评测
  • 测评结果:50
  • 用时:159ms
  • 内存:37812kb
  • [2024-08-22 13:59:24]
  • 提交

answer

// cf bits/extc++.h nonsense
#ifdef ONLINE_JUDGE
#define _EXT_CODECVT_SPECIALIZATIONS_H 1
#define _EXT_ENC_FILEBUF_H 1
#endif
#include "bits/extc++.h"

using namespace std;

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t;
    ((cerr << " | " << u), ...);
    cerr << endl;
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__)
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

using ll = long long;

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

inline void init_io() {
    cin.tie(nullptr);
    cin.exceptions(ios::failbit);
    ios_base::sync_with_stdio(false);
}

template <typename T>
vector<T> iota(int n, const T& x) {
    vector<T> arr(n);
    iota(begin(arr), end(arr), x);
    return arr;
}

template <typename T>
ostream& operator<<(ostream& out, const vector<T>& arr) {
    out << "[";
    for (int i = 0; i < sz(arr); i++) {
        if (i) {
            out << ", ";
        }
        out << arr[i];
    }
    return out << "]";
}

template <typename T>
int c_lb(const vector<T>& arr, const T& x) {
    return int(lower_bound(begin(arr), end(arr), x) - begin(arr));
}

template <typename T>
int c_ub(const vector<T>& arr, const T& x) {
    return int(upper_bound(begin(arr), end(arr), x) - begin(arr));
}

template <typename T>
T reversed(T arr) {
    reverse(begin(arr), end(arr));
    return arr;
}

template <typename T>
T sorted(T arr) {
    sort(begin(arr), end(arr));
    return arr;
}

template <typename T>
bool on(T mask, int bit) {
    return (mask >> bit) & 1;
}

template <typename A, typename B>
ostream& operator<<(ostream& out, const pair<A, B>& p) {
    return out << "(" << p.first << ", " << p.second << ")";
}

vector<vector<pair<int, int>>> graph;

struct Solver {
    int m;
    vector<bool> ans, edge_vis;

    Solver(const vector<pair<int, int>>& edges) : m(sz(edges)), ans(m), edge_vis(m) {
        for (auto& [u, v] : edges) {
            graph[u].clear();
            graph[v].clear();
        }

        for (int i = 0; i < m; i++) {
            auto& [u, v] = edges[i];
            graph[u].emplace_back(v, i);
            graph[v].emplace_back(u, ~i);
        }

        for (auto& [u, v] : edges) {
            dfs(u);
            dfs(v);
        }
    }

    void dfs(int u) {
        while (sz(graph[u])) {
            auto [v, sei] = graph[u].back();
            graph[u].pop_back();

            int ei = sei < 0 ? ~sei : sei;

            if (edge_vis[ei]) {
                continue;
            }
            edge_vis[ei] = true;

            ans[ei] = sei < 0;
            dfs(v);
        }
    }
};

void solve(vector<vector<int>>& arr, int yl, int yr) {
    if (yr - yl == 1) {
        return;
    }

    int ym = (yl + yr) / 2;

    vector<pair<int*, int*>> edge_ptrs;
    vector<pair<int, int>> edges;

    for (auto& a : arr) {
        for (int i = 0; i < ym - yl; i++) {
            int* ca = &a[yl + i], *cb = &a[ym + i];

            edge_ptrs.emplace_back(ca, cb);
            edges.emplace_back(*ca, *cb);
        }
    }

    auto e_ans = Solver(edges).ans;

    for (int i = 0; i < sz(e_ans); i++) {
        if (e_ans[i]) {
            auto& [u, v] = edge_ptrs[i];
            swap(*u, *v);
        }
    }

    solve(arr, yl, ym);
    solve(arr, ym, yr);
}

void solve() {
    int n, m, nt;
    cin >> n >> m >> nt;

    graph.resize(nt);

    vector arr(n, vector(m, 0));
    for (auto& a : arr) {
        for (auto& b : a) {
            cin >> b;
            b--;
        }
    }

    solve(arr, 0, m);

    for (auto& a : arr) {
        for (int i = 0; i < m; i++) {
            cout << a[i] + 1 << " \n"[i == m - 1];
        }
    }
}

int main() {
    init_io();
    solve();
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

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

input:

3 2 3
1 2
2 3
2 3

output:

1 2
3 2
2 3

result:

ok 

Test #2:

score: 0
Wrong Answer
time: 0ms
memory: 3552kb

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:

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

result:

wrong answer 

Subtask #2:

score: 15
Accepted

Test #8:

score: 15
Accepted
time: 40ms
memory: 20736kb

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
29061 63866
63612 53683
78264 70370
76881 42647
31741 39251
61186 66491
65819 57686
53278 59145
26052 71962
81040 55279
51310 50859
24546 46800
85013 91165
21890 61530
84003 29099
86182 33573
10639 49212
91851 97312
14067 57682
69674 5243
62508 99007
26290 55524
43794 15519
5...

result:

ok 

Test #9:

score: 15
Accepted
time: 27ms
memory: 21072kb

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 47
47 48
48 49
49 50
50 51
51 52
52 53
53 54...

result:

ok 

Test #10:

score: 15
Accepted
time: 24ms
memory: 21108kb

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 47
47 48
48 49
49 50
50 51
51 52
52 53
53 54...

result:

ok 

Test #11:

score: 15
Accepted
time: 37ms
memory: 20856kb

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
75021 23663
67175 78883
90698 3919
67504 20718
49374 44011
1660 3236
71971 79270
24502 90540
54202 9732
88659 14395
52635 56600
21912 17986
56526 92420
40254 3472
64330 20431
9381 56003
57750 45529
45230 9388
83797 53437
75562 47526
45219 63126
87437 71020
50298 2016
43667 21982
8579 374...

result:

ok 

Test #12:

score: 15
Accepted
time: 37ms
memory: 17240kb

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
18759 19981
8681 2642
4102 18080
11473 16749
15290 690
17900 16229
17481 10684
12171 6328
1150 9417
5689 7185
17102 10346
9727 17958
13756 2117
13157 10955
2840 245
5257 5337
6429 16622
17516 10772
13007 19349
11359 2821
14341 8897
2482 3974
16241 17966
15458 18146
3345 15868
18630 14507...

result:

ok 

Test #13:

score: 15
Accepted
time: 26ms
memory: 18048kb

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
10 3
8 10
1 8
5 2
3 6
6 3
3 5
8 6
7 7
4 7
3 1
7 6
5 10
6 4
9 9
4 8
2 9
6 1
10 7
1 10
7 9
9 6
9 6
10 3
10 10
6 2
7 7
6 5
3 8
4 4
2 5
5 8
8 2
10 9
8 3
7 4
2 2
9 8
8 10
8 9
1 2
5 1
4 7
9 4
9 6
10 8
4 2
6 3
1 4
2 10
3 5
10 7
7 1
4 10
6 6
1 4
8 4
10 9
3 9
5 5
6 1
2 9
7 2
9 5
9 8
1 3
5 6
3 7
4 1
8 5
5...

result:

ok 

Test #14:

score: 15
Accepted
time: 29ms
memory: 20476kb

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
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 53479
33386 53479
6198 53479
4838...

result:

ok 

Test #15:

score: 15
Accepted
time: 32ms
memory: 20784kb

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
79073 63660
20397 41795
84311 1296
21178 3690
31611 21052
14323 51423
82468 34208
83835 2785
28274 50594
59957 10993
34259 64334
73934 89407
61083 14947
89472 53201
61243 33351
58718 76632
85318 67464
54224 45096
76529 84552
44253 30697
3108 43669
26489 64691
85776 79840
10620 7691
69960 ...

result:

ok 

Test #16:

score: 15
Accepted
time: 32ms
memory: 16216kb

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 85787
73684 41994
5614...

result:

ok 

Test #17:

score: 15
Accepted
time: 24ms
memory: 21136kb

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 15211
6670 74551
42121...

result:

ok 

Test #18:

score: 15
Accepted
time: 36ms
memory: 21032kb

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
53385 1393
48048 49825
568...

result:

ok 

Subtask #3:

score: 0
Wrong Answer

Dependency #2:

100%
Accepted

Test #19:

score: 5
Accepted
time: 31ms
memory: 20732kb

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
29061 63866
63612 53683
78264 70370
76881 42647
31741 39251
61186 66491
65819 57686
53278 59145
26052 71962
81040 55279
51310 50859
24546 46800
85013 91165
21890 61530
84003 29099
86182 33573
10639 49212
91851 97312
14067 57682
69674 5243
62508 99007
26290 55524
43794 15519
5...

result:

ok 

Test #20:

score: 5
Accepted
time: 20ms
memory: 21008kb

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 47
47 48
48 49
49 50
50 51
51 52
52 53
53 54...

result:

ok 

Test #21:

score: 5
Accepted
time: 24ms
memory: 20928kb

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 47
47 48
48 49
49 50
50 51
51 52
52 53
53 54...

result:

ok 

Test #22:

score: 0
Wrong Answer
time: 37ms
memory: 18740kb

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
96580 5576
69601 74432
5497 90724
61408 72215
86499 23207
29593 43465
49534 20236
95890 83680
35990 98338
14744 39222
72902 65183
73553 76527
27695 40936
68239 96356
20211 66861
9499 59817
65669 53200
74170 53434
44590 79062
45816 66321
32926 37251
26433 58003
72346 23461
6360...

result:

wrong answer 

Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 15
Accepted

Test #56:

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

input:

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

output:

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

result:

ok 

Test #57:

score: 15
Accepted
time: 0ms
memory: 4236kb

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:

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

result:

ok 

Test #58:

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

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 2 1
1 1429 1 1429
7 4 4 3
1430 3 3 1430
6 1 6 5
1431 5 5 1431
11 8 8 7
1432 7 7 1432
5 10 10 9
9 1433 9 1433
15 12 12 11
1434 11 11 1434
14 9 14 13
1435 13 13 1435
19 16 16 15
1436 15 15 1436
13 18 18 17
17 1437 17 1437
23 20 20 19
1438 19 19 1438
22 17 22 21
1439 21 21 1439
27 24 24 23
1440 23 ...

result:

ok 

Test #59:

score: 15
Accepted
time: 0ms
memory: 4484kb

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 1807
3618 1093
3471 359
3430 4...

result:

ok 

Test #60:

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

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 47
47 48
48 49
49 50
50 51
51 52
52 53
53 54...

result:

ok 

Test #61:

score: 15
Accepted
time: 0ms
memory: 4284kb

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 47
47 48
48 49
49 50
50 51
51 52
52 53
53 54...

result:

ok 

Test #62:

score: 15
Accepted
time: 3ms
memory: 4048kb

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:

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

result:

ok 

Test #63:

score: 15
Accepted
time: 0ms
memory: 4196kb

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:

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

result:

ok 

Test #64:

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

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

result:

ok 

Test #65:

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

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
2 1
1 2
1 1
1 1
2 1
1 1
1 2
2 1
1 2
2 1
2 2
1 2
2 2
2 1
1 2
...

result:

ok 

Test #66:

score: 15
Accepted
time: 0ms
memory: 4520kb

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
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
2806 2674
3636 2674
1254 2674
1143...

result:

ok 

Test #67:

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

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:

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

result:

ok 

Test #68:

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

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

result:

ok 

Test #69:

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

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

result:

ok 

Subtask #6:

score: 0
Wrong Answer

Dependency #5:

100%
Accepted

Test #70:

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

input:

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

output:

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

result:

ok 

Test #71:

score: 5
Accepted
time: 2ms
memory: 4304kb

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:

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

result:

ok 

Test #72:

score: 5
Accepted
time: 2ms
memory: 4244kb

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 2 1
1 1429 1 1429
7 4 4 3
1430 3 3 1430
6 1 6 5
1431 5 5 1431
11 8 8 7
1432 7 7 1432
5 10 10 9
9 1433 9 1433
15 12 12 11
1434 11 11 1434
14 9 14 13
1435 13 13 1435
19 16 16 15
1436 15 15 1436
13 18 18 17
17 1437 17 1437
23 20 20 19
1438 19 19 1438
22 17 22 21
1439 21 21 1439
27 24 24 23
1440 23 ...

result:

ok 

Test #73:

score: 5
Accepted
time: 2ms
memory: 4532kb

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 1807
3618 1093
3471 359
3430 4...

result:

ok 

Test #74:

score: 5
Accepted
time: 2ms
memory: 4592kb

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 47
47 48
48 49
49 50
50 51
51 52
52 53
53 54...

result:

ok 

Test #75:

score: 5
Accepted
time: 2ms
memory: 4304kb

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 47
47 48
48 49
49 50
50 51
51 52
52 53
53 54...

result:

ok 

Test #76:

score: 0
Wrong Answer
time: 3ms
memory: 4284kb

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:

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

result:

wrong answer 

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: 32ms
memory: 20800kb

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
29061 63866
63612 53683
78264 70370
76881 42647
31741 39251
61186 66491
65819 57686
53278 59145
26052 71962
81040 55279
51310 50859
24546 46800
85013 91165
21890 61530
84003 29099
86182 33573
10639 49212
91851 97312
14067 57682
69674 5243
62508 99007
26290 55524
43794 15519
5...

result:

ok 

Test #118:

score: 20
Accepted
time: 28ms
memory: 21064kb

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 47
47 48
48 49
49 50
50 51
51 52
52 53
53 54...

result:

ok 

Test #119:

score: 20
Accepted
time: 23ms
memory: 20980kb

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 47
47 48
48 49
49 50
50 51
51 52
52 53
53 54...

result:

ok 

Test #120:

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

input:

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

output:

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

result:

ok 

Test #121:

score: 20
Accepted
time: 3ms
memory: 4352kb

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:

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

result:

ok 

Test #122:

score: 20
Accepted
time: 3ms
memory: 4032kb

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:

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

result:

ok 

Test #123:

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

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

result:

ok 

Test #124:

score: 20
Accepted
time: 2ms
memory: 4248kb

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
2 1
1 2
1 1
1 1
2 1
1 1
1 2
2 1
1 2
2 1
2 2
1 2
2 2
2 1
1 2
...

result:

ok 

Test #125:

score: 20
Accepted
time: 2ms
memory: 4516kb

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
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
2806 2674
3636 2674
1254 2674
1143...

result:

ok 

Test #126:

score: 20
Accepted
time: 2ms
memory: 4292kb

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:

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

result:

ok 

Test #127:

score: 20
Accepted
time: 2ms
memory: 4328kb

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

result:

ok 

Test #128:

score: 20
Accepted
time: 37ms
memory: 20812kb

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
75021 23663
67175 78883
90698 3919
67504 20718
49374 44011
1660 3236
71971 79270
24502 90540
54202 9732
88659 14395
52635 56600
21912 17986
56526 92420
40254 3472
64330 20431
9381 56003
57750 45529
45230 9388
83797 53437
75562 47526
45219 63126
87437 71020
50298 2016
43667 21982
8579 374...

result:

ok 

Test #129:

score: 20
Accepted
time: 2ms
memory: 4352kb

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

result:

ok 

Test #130:

score: 20
Accepted
time: 2ms
memory: 4276kb

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:

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

result:

ok 

Test #131:

score: 20
Accepted
time: 2ms
memory: 4464kb

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 2 1
1 1429 1 1429
7 4 4 3
1430 3 3 1430
6 1 6 5
1431 5 5 1431
11 8 8 7
1432 7 7 1432
5 10 10 9
9 1433 9 1433
15 12 12 11
1434 11 11 1434
14 9 14 13
1435 13 13 1435
19 16 16 15
1436 15 15 1436
13 18 18 17
17 1437 17 1437
23 20 20 19
1438 19 19 1438
22 17 22 21
1439 21 21 1439
27 24 24 23
1440 23 ...

result:

ok 

Test #132:

score: 20
Accepted
time: 2ms
memory: 4416kb

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 1807
3618 1093
3471 359
3430 4...

result:

ok 

Test #133:

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

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 47
47 48
48 49
49 50
50 51
51 52
52 53
53 54...

result:

ok 

Test #134:

score: 20
Accepted
time: 2ms
memory: 4592kb

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 47
47 48
48 49
49 50
50 51
51 52
52 53
53 54...

result:

ok 

Test #135:

score: 20
Accepted
time: 132ms
memory: 36856kb

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 50005 61873 20321 41067 32071 15682 617
33172 47471 45992 17329 52336 8305 39927 22133
10649 42134 15289 19194 42551 55858 10715 45570
7073 12818 8176 20965 5735 13244 5527 61861
58752 11867 29108 9701 17636 21000 8783 42134
35793 4734 30422 7606 5665 41719 25545 53912
6540 43594 60834 7781 20...

result:

ok 

Test #136:

score: 20
Accepted
time: 159ms
memory: 33028kb

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:

215 476 366 265 113 178 200 418 262 419 27 405 467 294 335 97 296 275 90 299 68 291 277 385 382 130 259 112 196 223 484 7 248 127 438 173 234 456 186 247 409 358 306 93 426 383 466 461 252 353 406 239 402 342 448 143 74 432 340 48 356 189 386 170 470 482 147 198 100 236 439 9 422 213 72 41 146 184 1...

result:

ok 

Test #137:

score: 20
Accepted
time: 37ms
memory: 9220kb

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 5 1 6 1 6 6 5 2 1 5 6 6 2 6 5 6 5 6 2 6 5 5 1 1 2 6 5 2 6 5 5 1 2 6 6 2 6 5 5 6 2 1 5 1 5 6 5 2 1 6 5 6 5 1 6 6 2 5 5 6 1 5 5 2 1 5 6 2 6 5 6 2 1 6 6 1 5 6 5 5 6 1 5 2 6 5 6 1 6 2 5 6 1 5 5 1 2 6 5 2 5 6 1 1 5 2 6 6 5 5 6 2 1 6 5 6 5 5 6 1 2 5 6 6 5 5 6 5 2 1 6 2 6 5 6 1 6 5 6 2 5 6 1 6 5 2 1 1 6 ...

result:

ok 

Test #138:

score: 20
Accepted
time: 41ms
memory: 15328kb

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:

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

result:

ok 

Test #139:

score: 20
Accepted
time: 32ms
memory: 17260kb

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
18759 19981
8681 2642
4102 18080
11473 16749
15290 690
17900 16229
17481 10684
12171 6328
1150 9417
5689 7185
17102 10346
9727 17958
13756 2117
13157 10955
2840 245
5257 5337
6429 16622
17516 10772
13007 19349
11359 2821
14341 8897
2482 3974
16241 17966
15458 18146
3345 15868
18630 14507...

result:

ok 

Test #140:

score: 20
Accepted
time: 130ms
memory: 30584kb

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:

159 169 170 92 126 89 234 226 205 78 220 154 106 245 88 194 273 66 86 123 279 259 128 121 59 16 153 6 35 90 160 258 147 293 272 289 120 84 257 96 83 40 177 233 225 95 142 212 186 4 252 102 60 162 139 202 283 236 184 3 145 13 181 109 210 44 26 255 241 74 118 150 268 18 54 71 101 73 176 208 228 111 17...

result:

ok 

Test #141:

score: 20
Accepted
time: 121ms
memory: 35084kb

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 6924 37442 26908 28108 49331 2683 14021
8443 19287 4215 12234 33860 29554 37602 1201
48003 48979 30310 2040 24906 47930 2453 34206
37618 30112 35224 19079 23394 26155 37361 42351
18576 29106 48671 22449 7931 4011 19435 25578
23309 13442 3382 45122 24117 19031 7174 31964
41121 5388 33083 49016 1...

result:

ok 

Test #142:

score: 20
Accepted
time: 147ms
memory: 37812kb

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:

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

result:

ok 

Test #143:

score: 20
Accepted
time: 151ms
memory: 32748kb

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:

56 36 28 26 25 29 36 47 36 47 36 47 47 36 47 55 36 47 51 36 47 36 4 47 36 47 36 47 36 47 47 36 38 36 36 47 47 36 36 47 36 17 47 36 47 36 47 36 36 47 36 47 47 36 36 47 47 36 47 36 47 36 47 36 47 36 47 36 47 36 47 24 47 36 47 36 47 36 36 47 36 47 36 47 36 47 47 36 36 47 47 36 47 36 47 36 20 36 47 36 3...

result:

ok 

Test #144:

score: 20
Accepted
time: 125ms
memory: 28020kb

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:

29 20 47 22 40 36 40 48 40 33 49 20 20 18 27 20 40 14 40 20 20 40 40 20 40 20 40 20 20 40 40 20 35 8 20 44 40 20 20 40 40 20 20 40 40 20 40 20 40 20 40 20 20 40 20 40 20 40 20 40 20 40 20 40 40 20 20 40 20 40 20 13 20 40 20 40 20 40 20 40 20 40 20 40 20 40 20 40 20 40 20 40 20 40 20 40 40 20 40 20 2...

result:

ok 

Test #145:

score: 20
Accepted
time: 97ms
memory: 29860kb

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:

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

result:

ok 

Test #146:

score: 20
Accepted
time: 145ms
memory: 35760kb

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:

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

result:

ok 

Test #147:

score: 20
Accepted
time: 60ms
memory: 34572kb

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 28571 1
4 28572 28572 2
28573 1 28573 3
6 28574 28574 4
3 28575 28575 5
8 28576 28576 6
28577 5 28577 7
10 28578 28578 8
7 28579 28579 9
12 28580 28580 10
28581 9 28581 11
14 28582 28582 12
11 28583 28583 13
16 28584 28584 14
28585 13 28585 15
18 28586 28586 16
15 28587 28587 17
20 28588 285...

result:

ok 

Test #148:

score: 20
Accepted
time: 55ms
memory: 32500kb

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 2 1
1 57141 1 57141
7 4 4 3
57142 3 3 57142
6 1 6 5
57143 5 5 57143
11 8 8 7
57144 7 7 57144
5 10 10 9
9 57145 9 57145
15 12 12 11
57146 11 11 57146
14 9 14 13
57147 13 13 57147
19 16 16 15
57148 15 15 57148
13 18 18 17
17 57149 17 57149
23 20 20 19
57150 19 19 57150
22 17 22 21
57151 21 21 5715...

result:

ok 

Test #149:

score: 20
Accepted
time: 62ms
memory: 34792kb

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:

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

result:

ok 

Test #150:

score: 20
Accepted
time: 14ms
memory: 18140kb

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
10 3
8 10
1 8
5 2
3 6
6 3
3 5
8 6
7 7
4 7
3 1
7 6
5 10
6 4
9 9
4 8
2 9
6 1
10 7
1 10
7 9
9 6
9 6
10 3
10 10
6 2
7 7
6 5
3 8
4 4
2 5
5 8
8 2
10 9
8 3
7 4
2 2
9 8
8 10
8 9
1 2
5 1
4 7
9 4
9 6
10 8
4 2
6 3
1 4
2 10
3 5
10 7
7 1
4 10
6 6
1 4
8 4
10 9
3 9
5 5
6 1
2 9
7 2
9 5
9 8
1 3
5 6
3 7
4 1
8 5
5...

result:

ok 

Test #151:

score: 20
Accepted
time: 63ms
memory: 33924kb

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 99994 99993
42855 99995 42855 99995
99993 99992 99992 99989
42854 99993 99993 42854
99991 99990 99995 99990
42853 99991 99991 42853
99989 99988 99988 99985
42852 99989 99989 42852
99987 99986 99986 99991
42851 99987 42851 99987
99985 99984 99984 99981
42850 99985 99985 42850
99983 99982 ...

result:

ok 

Test #152:

score: 20
Accepted
time: 54ms
memory: 29208kb

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:

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

result:

ok 

Test #153:

score: 20
Accepted
time: 49ms
memory: 28764kb

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:

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

result:

ok 

Test #154:

score: 20
Accepted
time: 58ms
memory: 28888kb

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:

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

result:

ok 

Test #155:

score: 20
Accepted
time: 58ms
memory: 29172kb

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:

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

result:

ok 

Test #156:

score: 20
Accepted
time: 73ms
memory: 35080kb

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:

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

result:

ok 

Test #157:

score: 20
Accepted
time: 82ms
memory: 37604kb

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:

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

result:

ok 

Test #158:

score: 20
Accepted
time: 30ms
memory: 20496kb

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
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 53479
33386 53479
6198 53479
4838...

result:

ok 

Test #159:

score: 20
Accepted
time: 44ms
memory: 20908kb

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
79073 63660
20397 41795
84311 1296
21178 3690
31611 21052
14323 51423
82468 34208
83835 2785
28274 50594
59957 10993
34259 64334
73934 89407
61083 14947
89472 53201
61243 33351
58718 76632
85318 67464
54224 45096
76529 84552
44253 30697
3108 43669
26489 64691
85776 79840
10620 7691
69960 ...

result:

ok 

Test #160:

score: 20
Accepted
time: 38ms
memory: 16216kb

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 85787
73684 41994
5614...

result:

ok 

Test #161:

score: 20
Accepted
time: 32ms
memory: 21004kb

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 15211
6670 74551
42121...

result:

ok 

Test #162:

score: 20
Accepted
time: 36ms
memory: 21044kb

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
53385 1393
48048 49825
568...

result:

ok 

Subtask #9:

score: 0
Skipped

Dependency #3:

0%

Subtask #10:

score: 0
Skipped

Dependency #1:

0%