QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#890459#2789. Sortingthangthang100 ✓105ms20064kbC++172.6kb2025-02-08 23:43:252025-02-08 23:43:26

Judging History

This is the latest submission verdict.

  • [2025-02-08 23:43:26]
  • Judged
  • Verdict: 100
  • Time: 105ms
  • Memory: 20064kb
  • [2025-02-08 23:43:25]
  • Submitted

answer

#ifdef ONLINE_JUDGE

#include "sorting.h"

#endif // ONLINE_JUDGE

#include <bits/stdc++.h>

using namespace std;


int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]){

    int low = 1, high = M;

    while (low < high){
        int mid = low + high >> 1;

        vector <int> s(N);
        for (int i = 0; i < N; ++ i)
            s[i] = S[i];

        for (int i = 0; i < mid; ++ i)
            swap(s[X[i]], s[Y[i]]);

        vector <int> used(N, 0);
        int num = N;

        for (int i = 0; i < N; ++ i) if (!used[i]){
            num --;
            int u = i;
            while (!used[u]) used[u] = 1, u = s[u];
        }

        if (mid >= num) high = mid;
        else low = mid + 1;
    }

    //cerr << -1 << endl;

    vector <int> ord(N), pqh(N);
    iota(ord.begin(), ord.end(), 0);
    iota(pqh.begin(), pqh.end(), 0);

    for (int i = 0; i < low; ++ i){
        swap(ord[pqh[X[i]]], ord[pqh[Y[i]]]);
        swap(pqh[X[i]], pqh[Y[i]]);
    }

    vector <int> to(N);
    for (int i = 0; i < N; ++ i)
        to[ord[i]] = S[i];

    vector <int> used(N, 0);
    vector <pair <int, int>> ans;

    int needs = N;
    for (int i = 0; i < N; ++ i) if (!used[i]){
        int u = i;
        while (!used[u]){
            used[u] = 1;
            if (!used[to[u]]) ans.push_back({u, to[u]});
            u = to[u];

        }
        needs --;
    }

    vector <int> pos(N), s(N);
    for (int i = 0; i < N; ++ i)
        pos[S[i]] = i, s[i] = S[i];

    for (int i = 0; i < low; ++ i){
        swap(pos[s[X[i]]], pos[s[Y[i]]]);
        swap(s[X[i]], s[Y[i]]);
        if (i >= needs){
            P[i] = 0, Q[i] = 0;
            continue;
        }
        //cout << ans[i].first << ' ' << ans[i].second << endl;
        P[i] = pos[ans[i].first], Q[i] = pos[ans[i].second];
        swap(pos[s[P[i]]], pos[s[Q[i]]]);
        swap(s[P[i]], s[Q[i]]);
    }


    return low;
}



#ifndef ONLINE_JUDGE

const int MaxN = 2e5 + 5;

int N, S[MaxN], M, X[MaxN], Y[MaxN], P[MaxN], Q[MaxN];

int main(){
    cin >> N;
    for (int i = 0; i < N; ++ i)
        cin >> S[i];
    cin >> M;
    for (int i = 0; i < M; ++ i)
        cin >> X[i] >> Y[i];

    int R = findSwapPairs(N, S, M, X, Y, P, Q);
    cout << R << "\n";

    for (int i = 0; i < R; ++ i){
        swap(S[X[i]], S[Y[i]]);
        cout << P[i] << ' ' << Q[i] << "\n";
        swap(S[P[i]], S[Q[i]]);
    }

    for (int i = 0; i < N; ++ i)
        cout << S[i] << ' ';
}

#endif // ONLINE_JUDGE

/*
5
4 3 2 1 0
6
0 1
1 2
2 3
3 4
0 1
1 2

*/

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 8
Accepted

Test #1:

score: 8
Accepted
time: 1ms
memory: 3712kb

input:

1
0
1
0 0

output:

1
0 0

result:

ok correct

Test #2:

score: 8
Accepted
time: 1ms
memory: 3840kb

input:

2
0 1
4
0 0
0 0
0 0
0 0

output:

1
0 0

result:

ok correct

Test #3:

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

input:

2
1 0
4
0 0
0 0
0 0
0 0

output:

1
1 0

result:

ok correct

Test #4:

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

input:

3
1 0 2
9
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0

output:

1
1 0

result:

ok correct

Test #5:

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

input:

4
3 2 0 1
16
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0

output:

3
2 0
2 3
2 1

result:

ok correct

Test #6:

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

input:

5
1 4 2 3 0
25
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0

output:

2
4 0
4 1

result:

ok correct

Test #7:

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

input:

5
4 2 1 0 3
25
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0

output:

3
3 0
3 4
2 1

result:

ok correct

Subtask #2:

score: 12
Accepted

Test #8:

score: 12
Accepted
time: 0ms
memory: 3840kb

input:

1
0
30
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0

output:

1
0 0

result:

ok correct

Test #9:

score: 12
Accepted
time: 1ms
memory: 3840kb

input:

2
0 1
60
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0

output:

1
0 0

result:

ok correct

Test #10:

score: 12
Accepted
time: 1ms
memory: 3712kb

input:

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

output:

93
84 0
84 82
84 41
84 20
84 34
84 61
84 29
84 48
84 18
84 63
84 5
84 51
84 59
84 3
84 12
84 74
84 43
84 73
84 95
84 81
84 60
84 17
84 67
84 30
84 2
84 31
84 55
84 40
84 72
84 64
84 21
84 50
84 71
84 80
84 22
84 87
84 10
84 49
84 11
84 52
84 88
84 47
84 28
84 77
84 23
84 83
84 69
84 92
84 1
84 70
84...

result:

ok correct

Test #11:

score: 12
Accepted
time: 0ms
memory: 3840kb

input:

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

output:

92
3 0
3 8
3 50
3 26
3 9
3 93
3 56
3 30
3 67
3 65
3 19
3 38
3 25
3 7
3 10
3 49
3 22
3 42
3 97
3 51
3 63
3 69
3 13
3 2
61 1
61 14
61 54
61 11
61 23
61 83
61 32
61 68
61 33
61 5
61 74
61 86
61 21
61 36
61 34
61 70
61 52
61 77
61 43
61 48
61 87
61 16
61 90
61 44
61 29
61 62
61 96
61 91
61 76
61 92
61 5...

result:

ok correct

Test #12:

score: 12
Accepted
time: 1ms
memory: 3712kb

input:

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

output:

95
60 0
60 12
60 82
60 72
60 65
60 2
60 75
60 66
60 3
60 59
60 51
60 56
60 46
60 90
60 71
60 6
60 52
60 20
60 80
60 14
60 85
60 18
60 57
60 22
60 34
60 32
60 89
60 73
60 92
60 48
60 35
60 70
60 5
60 30
60 81
60 86
60 38
60 43
60 36
60 26
60 47
60 42
60 94
60 61
60 69
60 76
60 15
60 78
60 10
60 93
60...

result:

ok correct

Subtask #3:

score: 16
Accepted

Test #13:

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

input:

2
0 1
60
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1

output:

1
1 0

result:

ok correct

Test #14:

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

input:

5
0 4 1 3 2
150
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
...

output:

2
2 0
2 4

result:

ok correct

Test #15:

score: 16
Accepted
time: 1ms
memory: 3840kb

input:

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

output:

91
79 0
79 15
79 66
79 91
79 18
79 64
79 31
79 61
79 67
79 49
79 78
79 85
79 89
79 26
79 69
79 43
79 57
79 33
79 94
79 72
79 87
79 13
79 71
79 8
79 81
79 92
79 82
79 74
79 16
79 44
79 34
79 14
79 63
79 41
79 37
79 86
79 30
79 60
79 62
79 77
79 46
79 10
79 58
79 38
79 68
79 51
79 93
79 83
79 47
79 88...

result:

ok correct

Test #16:

score: 16
Accepted
time: 1ms
memory: 3840kb

input:

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

output:

92
42 1
42 28
42 83
42 78
42 62
42 8
42 18
42 66
42 13
42 4
42 73
42 70
42 79
42 27
42 15
42 49
42 50
42 14
42 40
42 92
42 54
42 98
42 11
42 69
81 0
81 2
81 16
81 33
81 41
81 57
81 60
81 39
81 9
81 46
81 32
61 3
61 95
61 91
61 20
61 97
61 93
61 26
61 67
61 85
61 37
61 87
61 63
61 74
61 10
61 82
61 8...

result:

ok correct

Test #17:

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

input:

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

output:

97
83 1
83 52
83 81
83 7
83 75
83 5
83 87
83 19
83 56
83 72
83 3
83 91
83 90
83 61
83 53
83 14
83 62
83 6
83 65
83 45
83 46
83 63
83 37
83 66
83 96
83 10
83 64
83 44
83 4
83 38
83 12
83 95
83 73
83 82
83 27
83 68
83 2
83 59
83 88
83 54
83 50
83 42
83 43
83 40
83 92
83 89
83 18
83 47
83 57
83 34
83 1...

result:

ok correct

Test #18:

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

input:

4
0 1 3 2
120
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 ...

output:

2
3 2
0 0

result:

ok correct

Subtask #4:

score: 18
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #19:

score: 18
Accepted
time: 0ms
memory: 3840kb

input:

1
0
30
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0

output:

1
0 0

result:

ok correct

Test #20:

score: 18
Accepted
time: 0ms
memory: 3840kb

input:

2
0 1
60
1 0
0 1
1 0
0 1
1 0
0 1
1 0
0 1
0 1
1 0
0 1
0 1
1 0
0 1
0 1
0 1
1 0
1 0
0 1
1 0
0 1
1 0
1 0
1 0
1 0
1 0
0 1
0 1
0 1
1 0
1 0
1 0
1 0
1 0
1 0
1 0
0 1
1 0
0 1
1 0
0 1
1 0
0 1
1 0
1 0
0 1
1 0
1 0
0 1
1 0
1 0
0 1
0 1
0 1
0 1
1 0
0 1
1 0
1 0
1 0

output:

1
1 0

result:

ok correct

Test #21:

score: 18
Accepted
time: 0ms
memory: 3840kb

input:

481
264 22 307 266 238 227 68 26 13 12 384 162 410 306 374 311 442 38 407 310 280 308 333 146 326 381 367 110 190 33 141 468 153 393 157 415 229 75 276 392 349 348 179 445 317 64 78 20 323 257 292 395 129 259 165 398 151 219 14 116 338 188 243 61 150 84 72 340 155 133 459 464 248 433 124 399 177 62 ...

output:

473
426 118
426 381
426 307
426 144
426 186
426 167
426 242
426 328
426 41
426 437
426 63
426 457
426 276
426 209
426 380
426 292
426 31
426 388
426 311
426 293
426 21
426 26
426 214
426 347
426 448
426 239
426 310
426 98
426 106
426 284
426 142
426 398
426 23
426 410
426 36
426 229
426 202
426 195
...

result:

ok correct

Test #22:

score: 18
Accepted
time: 1ms
memory: 3968kb

input:

478
458 446 125 326 318 327 263 67 453 296 46 116 270 440 323 38 181 235 415 412 95 365 133 397 157 441 348 223 459 449 149 168 59 107 171 262 328 450 289 314 141 139 29 393 211 477 146 239 433 142 269 145 342 155 238 172 206 23 108 31 48 117 180 424 50 147 325 468 161 291 272 130 93 472 245 207 154...

output:

476
253 374
253 436
253 119
253 195
253 161
253 446
253 187
253 167
253 189
253 258
253 407
253 456
253 150
253 210
253 273
253 121
253 158
253 305
253 141
253 112
253 242
253 311
253 303
253 127
253 77
253 428
253 181
253 48
253 413
253 347
253 309
253 370
253 382
253 469
253 388
253 236
253 125
25...

result:

ok correct

Test #23:

score: 18
Accepted
time: 0ms
memory: 3968kb

input:

496
426 495 20 100 83 50 3 247 94 52 290 45 179 160 344 239 270 133 492 398 131 476 271 436 69 351 401 494 111 76 393 432 431 207 53 350 24 288 278 359 413 253 181 166 186 336 35 173 209 448 352 364 188 434 203 38 439 32 328 285 213 112 47 128 136 303 49 180 444 132 177 114 287 475 161 483 14 108 66...

output:

490
403 106
403 482
403 349
403 246
403 426
403 155
403 116
403 333
403 33
403 257
403 192
403 163
403 474
403 238
403 245
403 217
403 399
403 122
403 108
403 231
403 318
403 410
403 480
403 169
403 423
403 471
403 143
403 134
403 6
403 388
403 292
403 78
403 55
403 64
403 75
403 186
403 266
403 332...

result:

ok correct

Test #24:

score: 18
Accepted
time: 0ms
memory: 3968kb

input:

484
307 290 7 454 181 133 142 213 413 207 146 153 236 111 320 453 476 103 316 158 235 388 150 155 329 297 196 345 335 197 173 0 156 59 357 85 161 280 229 98 412 187 42 226 244 203 99 475 223 81 56 309 273 87 159 317 50 313 199 366 185 409 172 483 447 427 71 284 330 30 73 414 154 70 302 417 113 107 2...

output:

422
31 0
31 405
31 70
31 73
31 91
31 456
31 282
31 426
31 449
31 118
31 171
31 462
31 307
321 412
321 339
321 225
321 308
321 40
321 1
321 206
321 122
321 120
321 188
321 285
321 367
321 341
321 423
321 92
321 397
321 125
321 19
321 158
321 296
321 224
321 270
321 364
321 76
321 411
321 445
321 138
...

result:

ok correct

Test #25:

score: 18
Accepted
time: 1ms
memory: 3968kb

input:

496
145 300 465 228 235 186 373 183 142 208 278 11 410 286 392 245 44 470 211 368 283 240 265 120 30 68 71 158 263 356 439 243 27 311 86 134 201 33 319 371 254 181 231 89 214 435 113 59 48 151 317 143 320 195 377 426 408 303 22 47 149 330 180 175 412 140 102 204 381 441 50 258 232 105 266 52 122 423...

output:

145
465 2
198 228
235 4
438 12
438 410
392 14
471 470
239 19
283 20
240 21
165 23
165 120
258 71
32 27
32 158
282 263
24 30
37 33
110 34
110 86
476 35
319 38
363 40
342 42
342 231
89 43
435 45
113 46
70 50
70 317
95 195
148 54
148 377
417 55
417 426
406 303
265 58
330 61
446 65
446 140
325 102
117 6...

result:

ok correct

Test #26:

score: 18
Accepted
time: 1ms
memory: 3968kb

input:

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

output:

270
1 246
1 89
1 17
1 233
1 132
1 436
1 376
1 298
1 290
1 163
1 189
1 265
1 197
1 453
1 102
1 28
1 270
1 174
1 393
1 227
1 470
1 159
1 266
1 262
1 255
1 148
1 112
1 456
1 462
1 127
1 319
1 368
1 256
1 82
2 277
2 190
2 381
2 21
2 211
2 238
2 381
2 49
2 49
2 380
2 360
335 355
335 384
335 396
335 193
3...

result:

ok correct

Test #27:

score: 18
Accepted
time: 1ms
memory: 3968kb

input:

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

output:

473
0 361
0 285
0 136
0 121
0 219
0 282
0 137
0 444
0 77
0 152
0 273
0 264
0 316
0 156
0 313
0 167
0 388
0 314
0 35
0 42
0 57
0 329
0 274
0 127
0 146
0 199
0 337
0 408
0 141
0 111
0 357
0 233
0 464
0 181
0 457
0 201
0 18
0 61
0 8
0 287
0 251
0 435
0 81
0 384
0 367
0 36
0 359
0 100
0 118
0 456
0 415
...

result:

ok correct

Subtask #5:

score: 20
Accepted

Test #28:

score: 20
Accepted
time: 1ms
memory: 3968kb

input:

1800
530 1775 466 953 230 1179 944 752 990 1316 275 1029 158 152 1673 1706 172 115 599 1661 131 699 1112 454 551 1059 291 495 28 67 773 480 839 462 1210 757 879 285 439 3 1429 820 26 1023 942 199 356 625 1705 1421 144 1529 716 7 1485 1027 1599 696 517 1353 456 1389 273 1363 1414 1177 718 41 777 1621...

output:

1794
688 0
688 530
688 288
688 1704
688 346
688 1543
688 941
688 475
688 576
688 965
688 1091
688 194
688 1005
688 1734
688 1664
688 139
688 1736
688 1406
688 713
688 1157
688 1310
688 1342
688 1323
688 1671
688 1156
688 1727
688 486
688 633
688 513
688 1499
688 104
688 1712
688 260
688 1248
688 117...

result:

ok correct

Test #29:

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

input:

1950
1718 335 1071 714 1080 1828 1472 410 553 1269 297 401 1021 621 1763 528 205 1231 406 5 715 876 1474 1110 653 862 838 291 1092 549 955 1334 1044 300 1070 720 1877 484 1597 1948 1078 28 87 1193 505 1024 1259 63 852 960 633 1573 713 504 15 820 1852 752 1601 1168 471 1903 499 693 1209 1492 56 908 9...

output:

1944
1223 0
1223 1718
1223 1717
1223 688
1223 1910
1223 683
1223 969
1223 625
1223 692
1223 1932
1223 1788
1223 1452
1223 580
1223 1787
1223 898
1223 794
1223 1648
1223 551
1223 884
1223 518
1223 595
1223 1337
1223 1890
1223 591
1223 1801
1223 1364
1223 198
1223 1444
1223 1883
1223 1942
1223 1464
12...

result:

ok correct

Test #30:

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

input:

1853
452 1299 444 1527 510 1801 34 1178 1589 1782 342 1800 735 761 879 999 1122 1772 236 566 1459 1256 1149 1498 1827 1027 715 1377 6 306 1811 950 500 890 196 1825 1568 1157 943 1422 475 1237 1792 1796 1363 1217 889 968 1439 1116 322 795 1088 1358 1833 96 118 543 1337 207 876 1144 805 215 1433 903 1...

output:

1844
1354 1804
1354 1019
1354 248
1354 462
1354 1795
1354 1216
1354 1583
1354 1826
1354 685
1354 319
1354 620
1354 144
1354 690
1354 86
1354 775
1354 1448
1354 244
1354 370
1354 504
1354 724
1354 1173
1354 866
1354 180
1354 1531
1354 305
1354 467
1354 1551
1354 554
1354 853
1354 801
1354 670
1354 23...

result:

ok correct

Test #31:

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

input:

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

output:

1
1541 840

result:

ok correct

Test #32:

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

input:

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

output:

134
5 540
25 1610
27 1604
39 1305
65 831
66 679
66 295
67 776
68 1991
69 121
71 1306
81 1381
90 101
93 1892
113 133
955 115
124 885
563 157
169 1479
200 1256
201 1739
205 1580
206 1896
206 1693
206 1200
210 1912
213 1583
1486 214
1486 1829
230 1057
237 460
245 271
245 1156
1383 248
250 1006
263 1957...

result:

ok correct

Test #33:

score: 20
Accepted
time: 1ms
memory: 3968kb

input:

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

output:

377
0 475
0 516
1 1156
1 591
1 848
5 355
5 640
18 1612
18 1317
18 1185
18 570
20 883
26 247
26 173
27 62
27 1638
27 593
27 508
27 420
27 1196
27 459
34 1504
39 855
39 199
39 1929
43 554
1259 46
1259 359
53 514
54 1017
56 389
59 870
59 336
59 1226
60 1205
63 178
63 1685
65 250
65 502
66 961
66 816
68...

result:

ok correct

Test #34:

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

input:

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

output:

1080
2 1901
2 229
2 192
2 1396
2 907
2 1983
2 1763
2 1526
2 1317
2 1969
2 579
2 242
2 1885
2 657
2 1411
2 352
2 1246
2 1461
2 606
2 767
2 1687
2 329
2 177
2 1264
2 1471
2 1766
2 1171
2 1934
2 595
2 1274
2 1356
2 65
2 247
2 1218
2 590
2 1511
2 1059
2 1040
2 362
2 6
2 248
2 16
2 1013
2 1675
2 434
2 83...

result:

ok correct

Test #35:

score: 20
Accepted
time: 1ms
memory: 3968kb

input:

1901
952 410 986 1281 736 1411 1256 622 375 1423 718 1153 1238 643 120 1336 1097 881 1140 1395 1195 847 925 967 280 1859 966 360 815 770 634 1774 1359 1871 1589 618 991 571 1704 170 1548 1791 225 741 1561 35 1334 1632 203 894 728 1681 1849 22 1152 1719 701 1886 1037 1309 1576 993 1350 1643 893 1888 ...

output:

1897
1790 245
1790 1303
1790 673
1790 865
1790 124
1790 1400
1790 1220
1790 551
1790 91
1790 812
1790 1161
1790 276
1790 409
1790 379
1790 1560
1790 1723
1790 442
1790 480
1790 1599
1790 1273
1790 632
1790 183
1790 964
1790 82
1790 561
1790 1826
1790 1579
1790 1091
1790 434
1790 425
1790 43
1790 741...

result:

ok correct

Test #36:

score: 20
Accepted
time: 1ms
memory: 3840kb

input:

1931
1361 1614 1425 1627 1210 1778 166 420 1747 1792 1060 1914 611 833 1280 86 1754 1194 762 185 488 1368 1794 1153 1466 1689 1185 168 1622 1582 959 197 103 1809 1586 436 633 853 463 738 820 630 159 398 150 1370 558 281 1849 483 1691 350 1867 1871 1392 1791 1697 926 639 1865 1063 1726 262 1009 495 1...

output:

1923
1611 722
1611 1396
1611 1257
1611 760
1611 1869
1611 1486
1611 1062
1611 1006
1611 957
1611 1770
1611 279
1611 1661
1611 954
1611 1676
1611 680
1611 510
1611 71
1611 1316
1611 392
1611 116
1611 1542
1611 75
1611 1814
1611 636
1611 302
1611 563
1611 336
1611 746
1611 569
1611 967
1611 639
1611 1...

result:

ok correct

Test #37:

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

input:

1938
428 1641 1051 1154 1556 814 986 237 1557 1082 84 1382 1823 1591 1779 1565 193 574 1683 1259 405 393 366 644 612 562 303 1567 997 1422 868 132 74 1508 1002 965 1752 500 1148 529 1119 1841 930 1608 1472 310 1435 261 705 908 588 1710 722 1427 1825 1256 1175 379 45 902 1861 62 729 1303 759 766 1022...

output:

1928
1460 1202
1460 1706
1460 698
1460 976
1460 522
1460 1904
1460 1765
1460 413
1460 359
1460 1220
1460 666
1460 1540
1460 1075
1460 316
1460 809
1460 724
1460 1843
1460 103
1460 713
1460 1472
1460 1848
1460 1751
1460 662
1460 1006
1460 839
1460 1895
1460 1735
1460 373
1460 1541
1460 7
1460 450
146...

result:

ok correct

Test #38:

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

input:

1997
1053 110 1738 1025 1245 1257 472 471 13 1215 1811 1371 476 1631 1028 892 1191 20 1323 868 435 1063 870 758 1538 155 1105 27 987 1345 1228 1473 452 1092 1561 1874 1417 95 252 565 1315 1389 533 1078 1259 1440 772 0 1588 1750 1451 644 659 1161 173 200 1680 1040 1827 1567 1069 12 1730 866 1493 65 5...

output:

1693
47 0
47 1207
47 893
47 1053
47 30
47 1228
137 1
137 110
137 71
137 1749
137 1043
137 1822
137 569
137 180
137 1694
137 174
1603 2
1603 562
1603 308
1603 1320
1603 1677
1603 498
1603 625
1603 1417
1603 36
1603 1661
1603 1034
1603 1000
1603 497
1603 1692
1603 1814
1603 837
1603 96
1603 687
1603 3...

result:

ok correct

Test #39:

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

input:

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

output:

1091
1 1898
1 239
1 249
1 257
1 1136
1 1348
1 1067
1 221
1 71
1 1835
1 931
1 934
1 1934
1 1859
1 969
1 1357
1 1016
1 1618
1 585
1 1565
1 1928
1 327
1 645
1 1412
1 463
1 393
1 10
1 538
1 1368
1 434
1 877
1 1541
1 929
1 1658
1 288
1 1144
1 1199
1 989
1 1685
1 1269
1 1594
1 637
1 983
1 1829
1 151
1 785...

result:

ok correct

Test #40:

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

input:

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

output:

1959
0 59
0 1813
0 1624
0 902
0 107
0 837
0 1669
0 12
0 1280
0 1006
0 1690
0 386
0 134
0 583
0 1261
0 1176
0 1908
0 183
0 866
0 596
0 229
0 1796
0 1565
0 447
0 507
0 352
0 153
0 1703
0 1818
0 398
0 1917
0 1882
0 939
0 1340
0 1170
0 1095
0 496
0 1829
0 1412
0 1467
0 208
0 1616
0 317
0 1824
0 1076
0 4...

result:

ok correct

Test #41:

score: 20
Accepted
time: 1ms
memory: 3968kb

input:

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

output:

2
1779 1471
0 0

result:

ok correct

Subtask #6:

score: 26
Accepted

Dependency #5:

100%
Accepted

Test #42:

score: 26
Accepted
time: 81ms
memory: 19080kb

input:

176900
167810 159384 90550 63101 76883 19925 161149 18578 132157 136198 141834 156609 167914 129523 2878 165972 95279 65282 30261 94853 37236 41515 166488 123502 141101 86565 153657 72526 396 92614 23189 1661 167567 100107 155037 35542 99140 171977 171544 123048 107611 71527 111368 88756 149185 9360...

output:

176885
5823 0
5823 167810
5823 2442
5823 129909
5823 10456
5823 139016
5823 16821
5823 25194
5823 38200
5823 72113
5823 156123
5823 73507
5823 15987
5823 8779
5823 73201
5823 41963
5823 73728
5823 104548
5823 21921
5823 132871
5823 50262
5823 67776
5823 89205
5823 59769
5823 70978
5823 43252
5823 21...

result:

ok correct

Test #43:

score: 26
Accepted
time: 82ms
memory: 19236kb

input:

180601
172380 49504 27207 3423 41891 140536 126137 40192 90592 127987 124918 9486 152764 76028 76578 51283 40029 108361 93576 1341 36411 19763 103182 57530 103033 111456 32419 24822 89698 42054 101746 78793 103184 136054 135074 170297 146325 170251 21191 78975 68633 116257 103827 106102 162889 14512...

output:

180588
124503 0
124503 172380
124503 168244
124503 97345
124503 179767
124503 3522
124503 53384
124503 40305
124503 116195
124503 175196
124503 22381
124503 59886
124503 97301
124503 130722
124503 7410
124503 67366
124503 123979
124503 70729
124503 74345
124503 108401
124503 144895
124503 99570
1245...

result:

ok correct

Test #44:

score: 26
Accepted
time: 87ms
memory: 19616kb

input:

190000
155277 81364 16113 73641 59637 140074 33594 60852 167804 149502 15249 35894 69246 132504 37548 26618 81511 141393 147548 24346 7165 123128 175784 74022 121283 80377 116823 111912 149688 96762 34103 104558 142346 82209 136360 40339 28418 119696 9573 42868 81005 59704 115658 173964 158009 43922...

output:

189985
128206 6338
128206 146707
128206 41152
128206 65051
128206 170369
128206 171879
128206 134705
128206 42599
128206 112108
128206 189903
128206 12820
128206 142391
128206 161399
128206 58449
128206 173900
128206 133
128206 163695
128206 103882
128206 63886
128206 36462
128206 48540
128206 16104...

result:

ok correct

Test #45:

score: 26
Accepted
time: 39ms
memory: 16500kb

input:

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

output:

1
160057 48436

result:

ok correct

Test #46:

score: 26
Accepted
time: 87ms
memory: 17964kb

input:

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

output:

89748
2 78364
2 35842
2 9672
2 65683
2 71027
2 8319
2 21063
2 184974
2 43582
2 52244
3 178167
3 26246
3 75666
4 32977
4 192010
4 120858
5 161202
5 152290
5 177561
5 148422
5 41601
5 11783
5 69582
5 77206
5 76526
5 121294
5 153488
5 54045
5 94179
5 42303
5 136622
5 49271
5 20690
5 68754
5 176198
5 10...

result:

ok correct

Test #47:

score: 26
Accepted
time: 89ms
memory: 18216kb

input:

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

output:

100444
1 43027
1 60918
1 191912
1 112584
1 29121
1 5965
1 187333
1 35442
1 9484
1 96328
1 53623
1 91415
1 184199
1 189219
1 102511
1 155298
1 24510
1 53454
1 36471
1 128544
1 163798
1 34688
1 166282
1 1810
1 91270
1 210
1 29433
1 52821
1 176903
1 70251
1 18688
1 139323
1 107913
1 173627
1 179035
1 4...

result:

ok correct

Test #48:

score: 26
Accepted
time: 88ms
memory: 18224kb

input:

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

output:

102949
0 45437
0 113317
0 15314
0 130320
0 28357
0 86954
0 56867
0 140646
0 126919
0 126291
0 50834
1 82218
1 111436
1 78746
1 185065
1 67580
1 78965
1 66147
2 23204
2 55244
2 24779
2 72016
4 12788
4 6329
5 106408
5 93284
5 107460
5 57808
5 58783
5 170827
7 3604
7 135006
8 34034
10 163083
10 12124
1...

result:

ok correct

Test #49:

score: 26
Accepted
time: 80ms
memory: 19620kb

input:

193129
36602 123872 92038 45146 138692 111345 188441 38874 91571 40957 134717 29367 19348 43950 30107 169548 95423 20615 37890 24013 43534 56756 81846 81665 44142 51120 180128 191175 155099 72840 184568 93861 80314 90359 189897 714 93862 77927 44624 23382 86361 118437 115484 86518 100371 84582 12335...

output:

193113
109966 0
109966 123872
109966 75351
109966 118305
109966 96670
109966 8239
109966 130070
109966 125631
109966 187123
109966 151269
109966 60095
109966 126436
109966 180628
109966 12796
109966 63684
109966 9189
109966 72029
109966 156588
109966 104689
109966 59064
109966 55835
109966 45741
109...

result:

ok correct

Test #50:

score: 26
Accepted
time: 97ms
memory: 19952kb

input:

197082
28948 99935 148708 46451 122696 180672 62930 125162 102390 178828 36655 81146 108094 50099 58749 177353 187400 182745 51049 117239 46107 132994 126349 134844 20491 77064 156426 77316 106562 74474 181231 51810 115214 17483 98735 11537 154284 152530 31318 32324 150103 162145 377 111950 32190 84...

output:

197073
145461 0
145461 99936
145461 69870
145461 47187
145461 20668
145461 16450
145461 169317
145461 61373
145461 104142
145461 84498
145461 29276
145461 148425
145461 53247
145461 64833
145461 53969
145461 176038
145461 86522
145461 45511
145461 78034
145461 132258
145461 97032
145461 176118
14546...

result:

ok correct

Test #51:

score: 26
Accepted
time: 105ms
memory: 19712kb

input:

194300
41456 157650 130220 26552 100104 39688 171793 93878 171968 42386 15076 119236 116984 147030 178130 84543 41422 78012 62905 182069 27860 51578 123684 182555 79509 132548 171199 184307 163260 137221 40321 193521 22658 163921 153451 81135 146421 61739 37826 184064 100949 1221 27789 179291 15206 ...

output:

194290
49723 0
49723 41456
49723 127559
49723 47547
49723 34824
49723 189317
49723 97502
49723 36639
49723 120581
49723 185290
49723 136251
49723 44453
49723 93233
49723 123611
49723 9477
49723 174033
49723 138813
49723 61783
49723 26823
49723 102272
49723 151312
49723 181653
49723 15326
49723 18350...

result:

ok correct

Test #52:

score: 26
Accepted
time: 97ms
memory: 19716kb

input:

191745
86160 177973 190897 101427 58207 52429 103273 57783 65873 49221 161353 23941 99019 125297 40852 27805 14133 40994 81091 37037 21432 47533 119915 102063 92390 79753 118310 157456 132054 38761 115430 33036 71721 54738 176381 140861 147078 36903 123109 71733 46877 173730 187571 7820 33867 26827 ...

output:

191732
150103 63702
150103 102245
150103 178160
150103 126792
150103 73223
150103 117546
150103 146663
150103 180892
150103 39341
150103 145938
150103 67540
150103 61612
150103 131999
150103 8754
150103 57037
150103 146041
150103 144943
150103 128678
150103 145318
150103 103747
150103 23994
150103 1...

result:

ok correct

Test #53:

score: 26
Accepted
time: 89ms
memory: 18220kb

input:

199993
196446 158206 8206 10499 39868 129031 121632 148457 183086 75548 11957 13065 15359 17847 118402 17577 159823 30468 24361 103231 121626 59655 36996 187439 89929 192793 20197 28808 16555 137308 105716 56425 198490 164384 8584 47629 83558 155060 148041 175988 3886 132588 15792 32028 104991 14846...

output:

99996
99339 0
99339 196446
99339 101789
99339 129894
99339 32635
99339 39319
99339 21631
99339 83562
99339 118012
99339 194794
99339 128307
99339 49435
99339 46625
99339 5331
99339 167664
99339 67990
99339 192319
99339 162310
99339 123627
99339 12784
99339 65632
99339 7866
99339 134293
99339 196934
...

result:

ok correct

Test #54:

score: 26
Accepted
time: 80ms
memory: 17984kb

input:

195962
0 143495 94457 139954 64590 53700 118663 178237 93365 76238 190312 47039 180296 27740 3019 173316 180035 69779 93653 122287 57697 21 119951 130009 15368 145558 129234 63611 55030 29 189665 107778 157921 184944 79827 118642 86050 82957 86225 39 29493 124696 114418 173586 84617 177846 170864 11...

output:

84206
56335 1
56335 143495
56335 148363
56335 29310
56335 181952
56335 19282
56335 109813
56335 151571
56335 86790
56335 136930
56335 186627
56335 55396
56335 24886
56335 74252
56335 152247
56335 182883
56335 12945
56335 44337
56335 82085
56335 124424
56335 135405
56335 79585
56335 150078
56335 4579...

result:

ok correct

Test #55:

score: 26
Accepted
time: 92ms
memory: 19848kb

input:

194842
100154 140138 48998 98453 130678 177133 46195 8423 62509 72873 77452 122206 42181 60275 170586 2358 7988 89849 185284 193691 59370 185794 5218 23270 118843 81380 57130 150638 52947 187734 187310 168413 153988 136321 38186 163329 189331 126207 137943 84857 145378 167961 161479 69302 31915 1202...

output:

182153
190730 0
190730 100154
190730 95131
190730 27280
190730 135143
190730 189310
190730 114024
190730 162064
190730 158889
190730 170024
190730 78028
190730 136058
190730 36032
190730 14067
190730 96467
190730 11605
190730 95869
190730 89014
190730 1170
190730 37977
190730 42369
190730 27472
1907...

result:

ok correct

Test #56:

score: 26
Accepted
time: 91ms
memory: 19768kb

input:

192864
140597 66570 121427 116752 26792 80717 160186 76426 8 89413 178636 77175 26030 47446 80214 37113 6890 186652 99224 16670 42488 160907 6475 13753 93053 55091 124543 86129 121212 126899 190219 159959 130785 94656 182197 40626 190748 71684 29400 127366 187275 144333 66541 159353 56469 45 46 1133...

output:

165493
81100 0
81100 168482
81100 97123
81100 112021
81100 127924
81100 132514
81100 69346
81100 165008
81100 97351
81100 47707
81100 73530
81100 124293
81100 104878
81100 10651
81100 154164
81100 33029
81100 177445
81100 19433
81100 54445
81100 27168
81100 91173
81100 46925
81100 117434
81100 55197...

result:

ok correct

Test #57:

score: 26
Accepted
time: 59ms
memory: 18276kb

input:

197205
69791 7278 144655 44140 100294 77302 123723 171433 104856 173242 169410 67899 36966 171145 136488 47079 48081 152021 59592 5911 4574 162108 173932 54582 62863 110098 59669 47193 129654 106687 152256 89688 184321 178761 50076 26558 84676 120349 3492 76839 83222 138603 78108 16086 42321 191702 ...

output:

49301
7278 1
144655 2
44140 3
100294 4
77302 5
123723 6
104856 8
173242 9
67899 11
171145 13
47079 15
152021 17
5911 19
173932 22
62863 24
59669 26
47193 27
89688 31
184321 32
178761 33
26558 35
120349 37
3492 38
76839 39
16086 43
191702 45
87915 47
101863 48
13181 49
283 50
178223 52
69114 55
43557...

result:

ok correct

Test #58:

score: 26
Accepted
time: 91ms
memory: 19952kb

input:

197131
84406 80027 110287 44746 131371 146934 42426 65970 150332 170783 65657 1953 162645 190993 109274 124958 51133 84371 52975 45289 169245 91663 107556 94239 181471 104596 71086 182854 165285 38597 66664 7262 124939 9815 82726 155117 130064 161982 165615 141978 54973 19100 50015 109085 117973 118...

output:

168671
84406 0
84406 84865
84406 6792
84406 85557
84406 72726
84406 48789
84406 143935
80027 1
110287 2
44746 3
131371 4
146934 66828
146934 76945
146934 44293
146934 136412
146934 112579
146934 30264
146934 174315
146934 15751
146934 152805
146934 133124
146934 122993
146934 165817
146934 30843
146...

result:

ok correct

Test #59:

score: 26
Accepted
time: 93ms
memory: 19672kb

input:

190716
70694 127495 127683 172932 35760 161055 89535 88848 86329 70488 159904 154657 123716 114250 17532 30359 18636 56168 87024 174259 84439 39232 146857 23700 109966 77964 87980 58575 44910 187918 44705 123208 129478 100467 24819 82211 54590 167945 186629 189101 150929 88606 28837 150355 60022 149...

output:

190706
3201 0
3201 70694
3201 153598
3201 179635
3201 110171
3201 69544
3201 25660
3201 179587
3201 17581
3201 83473
3201 14426
3201 29162
3201 131204
3201 169487
3201 47050
3201 19439
3201 119597
3201 83082
3201 13869
3201 121261
3201 60839
3201 6840
3201 1188
3201 52130
3201 88728
3201 104933
3201...

result:

ok correct

Test #60:

score: 26
Accepted
time: 100ms
memory: 19744kb

input:

193898
85269 174015 77811 28051 118737 97733 40719 89809 27239 143398 80856 147511 63066 169396 188622 137055 75691 19603 26753 21153 38282 19883 184352 116056 74924 109097 83545 91598 188816 130408 12005 58299 179552 132499 184991 172525 19246 46965 82109 14127 45042 61971 139287 156790 158325 1053...

output:

193877
175527 59438
175527 173698
175527 59400
175527 152126
175527 49910
175527 82582
175527 139558
175527 36722
175527 24955
175527 115201
175527 189825
175527 32733
175527 86085
175527 80691
175527 21242
175527 98030
175527 18138
175527 160841
175527 26949
175527 86861
175527 46553
175527 168674
...

result:

ok correct

Test #61:

score: 26
Accepted
time: 97ms
memory: 19780kb

input:

193451
73331 167267 1859 26632 182171 73089 171348 172101 254 125155 89420 155531 85116 116670 120195 104715 81962 173779 54516 70099 186190 71017 67533 23137 114603 120956 148961 4395 85938 127836 173745 186046 50370 28206 98366 112565 66018 46642 74053 48767 7112 15058 176808 908 73048 45225 60762...

output:

193228
126017 0
126017 73331
126017 157177
126017 47256
126017 165751
126017 162115
126017 62605
126017 94110
126017 15077
126017 157074
126017 80119
126017 83835
126017 146144
126017 16069
126017 125494
126017 82592
126017 121640
126017 33269
126017 165246
126017 163495
126017 38193
126017 21518
12...

result:

ok correct

Test #62:

score: 26
Accepted
time: 84ms
memory: 17744kb

input:

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

output:

95351
0 159419
0 84650
0 156008
0 133877
0 47932
0 62518
0 34269
0 94936
0 55439
0 134881
0 93548
0 150108
0 158345
0 187205
0 166803
0 33444
0 135960
0 98158
0 70948
0 64346
0 149828
0 131950
0 183346
0 174804
0 57592
0 32127
0 22437
0 33557
0 178113
2 113849
3 30017
3 147080
3 101652
4 110186
4 17...

result:

ok correct

Test #63:

score: 26
Accepted
time: 29ms
memory: 17404kb

input:

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

output:

2
139084 152764
0 0

result:

ok correct

Test #64:

score: 26
Accepted
time: 103ms
memory: 20064kb

input:

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

output:

199698
0 112395
0 77106
0 131593
0 198207
0 11975
0 36824
0 91202
0 104627
0 110565
0 168736
0 36713
0 131592
0 171328
0 72621
0 119521
0 123217
0 135224
0 100300
0 79986
0 39504
0 106460
0 159952
0 47062
0 75
0 67923
0 128437
0 176587
0 109367
0 92655
0 187440
0 113014
0 23801
0 75627
0 176152
0 16...

result:

ok correct

Test #65:

score: 26
Accepted
time: 97ms
memory: 19716kb

input:

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

output:

191784
0 117979
0 73089
0 144030
0 38264
0 36395
0 88337
0 160138
0 15394
0 45945
0 85190
0 30201
0 62542
0 33699
0 38654
0 47107
0 133688
0 143638
0 77972
0 155599
0 183819
0 168069
0 25337
0 19553
0 59451
0 74654
0 47936
0 94238
0 129124
0 69521
0 122387
0 104769
0 139903
0 63306
0 12532
0 176371
...

result:

ok correct

Test #66:

score: 26
Accepted
time: 95ms
memory: 19768kb

input:

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

output:

193069
0 162746
0 164541
0 38491
0 17133
0 185092
0 134620
0 109463
0 25187
0 123322
0 1730
0 39965
0 80180
0 13916
0 184582
0 174436
0 62384
0 162756
0 105812
0 41619
0 119188
0 32768
0 154342
0 31929
0 91814
0 50365
0 165681
0 86725
0 182090
0 33642
0 189555
0 158414
0 84188
0 66421
0 165817
0 836...

result:

ok correct