QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#266417#4317. 拯救还是毁灭jzh#AC ✓430ms49812kbC++201.8kb2023-11-26 14:01:282023-11-26 14:01:28

Judging History

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

  • [2023-11-26 14:01:28]
  • 评测
  • 测评结果:AC
  • 用时:430ms
  • 内存:49812kb
  • [2023-11-26 14:01:28]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

const int N = 1e3 + 5;
int a[N][N];

typedef pair<int, int> pii;
pii pos[N * N];
vector<pair<pii, pii>> ans;

void op(pii p1, pii p2) {
    if (p1 == p2)return;
    assert(p1.first == p2.first || p1.second == p2.second);
    int n1 = a[p1.first][p1.second], n2 = a[p2.first][p2.second];
    swap(pos[n1], pos[n2]);
    swap(a[p1.first][p1.second], a[p2.first][p2.second]);
    ans.emplace_back(p1, p2);
}

int main() {
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
            a[i][j]--;
            pos[a[i][j]] = {i, j};
        }
    }


    for (int i = 0; i < n; i++) {
        vector<int> cnt(n, 0);
        for (int j = 0; j < n; j++) {
            cnt[pos[i * n + j].second]++;
        }
        queue<int> q;
        for (int j = 0; j < n; j++) {
            if (cnt[j] == 0) {
                q.push(j);
            }
        }

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            int tar = i * n + u;
            cnt[pos[tar].second]--;
            if (cnt[pos[tar].second] == 0) {
                q.push(pos[tar].second);
            }
            op(pos[tar], {pos[tar].first, u});
            op(pos[tar], {i, pos[tar].second});
        }

        for (int j = 0; j < n; j++) {
            op(pos[i * n + j], {i, pos[i * n + j].second});

        }
        for (int j = 0; j < n; j++) {
            op(pos[i * n + j], {pos[i * n + j].first, j});
        }
    }


    cout << ans.size() << "\n";
    for(auto [p1,p2]:ans){
        cout << p1.first +1 <<" " << p1.second +1 <<" " << p2.first+1 <<" " << p2.second+1 <<"\n";
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 405ms
memory: 48452kb

input:

1000
921156 164917 876716 346601 859849 128010 597453 517820 153764 816228 42630 968115 720674 725887 873481 472730 923921 922689 526667 758819 770342 216266 971717 759305 966908 301482 74863 561426 880217 783710 560336 923860 491882 553154 530791 476240 818078 877946 148671 206130 898917 24153 5407...

output:

1998000
149 671 1 671
74 407 1 407
42 40 1 40
296 554 1 554
873 995 1 995
66 577 1 577
523 486 1 486
353 431 1 431
240 854 1 854
303 660 1 660
517 560 1 560
460 457 1 457
897 740 1 740
563 268 1 268
148 382 1 382
772 483 1 483
79 11 1 11
415 295 1 295
458 329 1 329
125 504 1 504
484 867 1 867
339 50...

result:

ok Accepted.

Test #2:

score: 0
Accepted
time: 414ms
memory: 49012kb

input:

1000
921156 164917 876716 346601 859849 128010 597453 517820 153764 816228 42630 968115 720674 725887 873481 472730 923921 922689 526667 758819 770342 216266 971717 759305 966908 301482 74863 561426 880217 783710 560336 923860 491882 553154 530791 476240 818078 877946 148671 206130 898917 24153 5407...

output:

1990052
149 671 1 671
74 407 1 407
42 40 1 40
296 554 1 554
873 995 1 995
66 577 1 577
523 486 1 486
353 431 1 431
240 854 1 854
303 660 1 660
517 560 1 560
460 457 1 457
897 740 1 740
563 268 1 268
148 382 1 382
772 483 1 483
79 11 1 11
415 295 1 295
458 329 1 329
125 504 1 504
484 867 1 867
339 50...

result:

ok Accepted.

Test #3:

score: 0
Accepted
time: 430ms
memory: 49476kb

input:

1000
921156 164917 876716 346601 859849 128010 597453 517820 153764 816228 42630 968115 720674 725887 873481 472730 923921 922689 526667 758819 770342 216266 971717 759305 966908 301482 74863 561426 880217 783710 560336 923860 491882 553154 530791 476240 818078 877946 148671 206130 898917 24153 5407...

output:

1990172
149 671 1 671
74 407 1 407
42 40 1 40
296 554 1 554
873 995 1 995
66 577 1 577
523 486 1 486
353 431 1 431
240 854 1 854
303 660 1 660
517 560 1 560
460 457 1 457
897 740 1 740
563 268 1 268
148 382 1 382
772 483 1 483
79 11 1 11
415 295 1 295
458 329 1 329
125 504 1 504
484 867 1 867
339 50...

result:

ok Accepted.

Test #4:

score: 0
Accepted
time: 416ms
memory: 48924kb

input:

1000
921156 164917 876716 346601 859849 128010 597453 517820 153764 816228 42630 968115 720674 725887 873481 472730 923921 922689 526667 758819 770342 216266 971717 759305 966908 301482 74863 561426 880217 783710 560336 923860 491882 553154 530791 476240 818078 877946 148671 206130 898917 24153 5407...

output:

1990184
149 671 1 671
74 407 1 407
42 40 1 40
296 554 1 554
873 995 1 995
66 577 1 577
523 486 1 486
353 431 1 431
240 854 1 854
303 660 1 660
517 560 1 560
460 457 1 457
897 740 1 740
563 268 1 268
148 382 1 382
772 483 1 483
79 11 1 11
415 295 1 295
458 329 1 329
125 504 1 504
484 867 1 867
339 50...

result:

ok Accepted.

Test #5:

score: 0
Accepted
time: 427ms
memory: 47976kb

input:

1000
921156 164917 876716 346601 859849 128010 597453 517820 153764 816228 42630 968115 720674 725887 873481 472730 923921 922689 526667 758819 770342 216266 971717 759305 966908 301482 74863 561426 880217 783710 560336 923860 491882 553154 530791 476240 818078 877946 148671 206130 898917 24153 5407...

output:

1990166
149 671 1 671
74 407 1 407
42 40 1 40
296 554 1 554
873 995 1 995
66 577 1 577
523 486 1 486
353 431 1 431
240 854 1 854
303 660 1 660
517 560 1 560
460 457 1 457
897 740 1 740
563 268 1 268
148 382 1 382
772 483 1 483
79 11 1 11
415 295 1 295
458 329 1 329
125 504 1 504
484 867 1 867
339 50...

result:

ok Accepted.

Test #6:

score: 0
Accepted
time: 407ms
memory: 48120kb

input:

1000
921156 164917 876716 346601 859849 128010 597453 517820 153764 816228 42630 968115 720674 725887 873481 472730 923921 922689 526667 758819 770342 216266 971717 759305 966908 301482 74863 561426 880217 783710 560336 923860 491882 553154 530791 476240 818078 877946 148671 206130 898917 24153 5407...

output:

1990098
149 671 1 671
74 407 1 407
42 40 1 40
296 554 1 554
873 995 1 995
66 577 1 577
523 486 1 486
353 431 1 431
240 854 1 854
303 660 1 660
517 560 1 560
460 457 1 457
897 740 1 740
563 268 1 268
148 382 1 382
772 483 1 483
79 11 1 11
415 295 1 295
458 329 1 329
125 504 1 504
484 867 1 867
339 50...

result:

ok Accepted.

Test #7:

score: 0
Accepted
time: 403ms
memory: 49660kb

input:

1000
921156 164917 876716 346601 859849 128010 597453 517820 153764 816228 42630 968115 720674 725887 873481 472730 923921 922689 526667 758819 770342 216266 971717 759305 966908 301482 74863 561426 880217 783710 560336 923860 491882 553154 530791 476240 818078 877946 148671 206130 898917 24153 5407...

output:

1989982
834 514 834 258
834 258 1 258
398 409 398 330
398 330 1 330
949 214 949 514
949 514 1 514
636 898 636 409
636 409 1 409
967 528 967 214
967 214 1 214
144 186 144 898
144 898 1 898
919 996 919 528
919 528 1 528
203 15 203 186
203 186 1 186
725 746 725 996
725 996 1 996
148 382 148 15
148 15 1...

result:

ok Accepted.

Test #8:

score: 0
Accepted
time: 402ms
memory: 49012kb

input:

1000
921156 164917 876716 346601 859849 128010 597453 517820 153764 816228 42630 968115 720674 725887 873481 472730 923921 922689 526667 758819 770342 216266 971717 759305 966908 301482 74863 561426 880217 783710 560336 923860 491882 553154 530791 476240 818078 877946 148671 206130 898917 24153 5407...

output:

1990118
834 514 834 258
834 258 1 258
398 409 398 330
398 330 1 330
607 556 607 380
607 380 1 380
276 226 276 816
276 816 1 816
264 36 264 862
264 862 1 862
949 214 949 514
949 514 1 514
636 898 636 409
636 409 1 409
86 922 86 556
86 556 1 556
19 311 19 226
19 226 1 226
212 4 212 36
212 36 1 36
967 ...

result:

ok Accepted.

Test #9:

score: 0
Accepted
time: 405ms
memory: 49400kb

input:

1000
921156 164917 876716 346601 859849 128010 597453 517820 153764 816228 42630 968115 720674 725887 873481 472730 923921 922689 526667 758819 770342 216266 971717 759305 966908 301482 74863 561426 880217 783710 560336 923860 491882 553154 530791 476240 818078 877946 148671 206130 898917 24153 5407...

output:

1990126
834 514 834 258
834 258 1 258
693 338 693 311
693 311 1 311
398 409 398 330
398 330 1 330
607 556 607 380
607 380 1 380
145 195 145 385
145 385 1 385
643 513 643 480
643 480 1 480
102 773 102 726
102 726 1 726
276 226 276 816
276 816 1 816
542 366 542 860
542 860 1 860
264 36 264 862
264 862...

result:

ok Accepted.

Test #10:

score: 0
Accepted
time: 414ms
memory: 48072kb

input:

1000
921156 164917 876716 346601 859849 128010 597453 517820 153764 816228 42630 968115 720674 725887 873481 472730 923921 922689 526667 758819 770342 216266 971717 759305 966908 301482 74863 561426 880217 783710 560336 923860 491882 553154 530791 476240 818078 877946 148671 206130 898917 24153 5407...

output:

1990194
97 792 97 116
97 116 1 116
522 75 522 234
522 234 1 234
834 514 834 258
834 258 1 258
693 338 693 311
693 311 1 311
398 409 398 330
398 330 1 330
607 556 607 380
607 380 1 380
145 195 145 385
145 385 1 385
850 287 850 442
850 442 1 442
643 513 643 480
643 480 1 480
102 773 102 726
102 726 1 ...

result:

ok Accepted.

Test #11:

score: 0
Accepted
time: 417ms
memory: 48376kb

input:

1000
921156 164917 876716 346601 859849 128010 597453 517820 153764 816228 42630 968115 720674 725887 873481 472730 923921 922689 526667 758819 770342 216266 971717 759305 966908 301482 74863 561426 880217 783710 560336 923860 491882 553154 530791 476240 818078 877946 148671 206130 898917 24153 5407...

output:

1990132
798 891 798 47
798 47 1 47
97 792 97 116
97 116 1 116
298 994 298 206
298 206 1 206
522 75 522 234
522 234 1 234
247 725 247 243
247 243 1 243
627 79 627 247
627 247 1 247
834 514 834 258
834 258 1 258
693 338 693 311
693 311 1 311
851 359 851 313
851 313 1 313
398 409 398 330
398 330 1 330
...

result:

ok Accepted.

Test #12:

score: 0
Accepted
time: 404ms
memory: 49488kb

input:

1000
921156 164917 876716 346601 859849 128010 597453 517820 153764 816228 42630 968115 720674 725887 873481 472730 923921 922689 526667 758819 770342 216266 971717 759305 966908 301482 74863 561426 880217 783710 560336 923860 491882 553154 530791 476240 818078 877946 148671 206130 898917 24153 5407...

output:

1998000
149 671 1 671
74 407 1 407
42 40 1 40
296 554 1 554
873 995 1 995
66 577 1 577
523 486 1 486
353 431 1 431
240 854 1 854
303 660 1 660
517 560 1 560
460 457 1 457
897 740 1 740
563 268 1 268
148 382 1 382
772 483 1 483
79 11 1 11
415 295 1 295
458 329 1 329
125 504 1 504
484 867 1 867
339 50...

result:

ok Accepted.

Test #13:

score: 0
Accepted
time: 416ms
memory: 48876kb

input:

1000
921156 164917 876716 346601 859849 128010 597453 517820 153764 816228 42630 968115 720674 725887 873481 472730 923921 922689 526667 758819 770342 216266 971717 759305 966908 301482 74863 561426 880217 783710 560336 923860 491882 742824 530791 476240 818078 877946 148671 206130 898917 24153 5407...

output:

1989924
662 428 662 41
662 41 1 41
204 701 204 46
204 46 1 46
798 891 798 47
798 47 1 47
75 59 75 70
75 70 1 70
97 792 97 116
97 116 1 116
365 126 365 153
365 153 1 153
331 562 331 188
331 188 1 188
178 945 178 203
178 203 1 203
298 994 298 206
298 206 1 206
522 75 522 234
522 234 1 234
247 725 247 ...

result:

ok Accepted.

Test #14:

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

input:

1
1

output:

0

result:

ok Accepted.

Test #15:

score: 0
Accepted
time: 397ms
memory: 49552kb

input:

1000
921156 164917 876716 346601 859849 128010 597453 517820 153764 816228 42630 968115 720674 725887 873481 472730 923921 922689 526667 758819 770342 216266 971717 759305 966908 301482 74863 561426 880217 783710 560336 923860 491882 553154 530791 476240 818078 877946 148671 206130 898917 24153 5407...

output:

1998000
149 671 1 671
74 407 1 407
42 40 1 40
296 554 1 554
873 995 1 995
66 577 1 577
523 486 1 486
353 431 1 431
240 854 1 854
303 660 1 660
517 560 1 560
460 457 1 457
897 740 1 740
563 268 1 268
148 382 1 382
772 483 1 483
79 11 1 11
415 295 1 295
458 329 1 329
125 504 1 504
484 867 1 867
339 50...

result:

ok Accepted.

Test #16:

score: 0
Accepted
time: 367ms
memory: 48752kb

input:

1000
378384 378846 378682 378036 378770 378725 378196 378111 378658 378211 378017 378043 378227 378651 378186 378791 378110 378138 378837 378271 378323 378843 378059 378762 378664 378389 378509 378691 378051 378238 378099 378118 378596 378364 378915 378862 378453 378342 378431 378003 378284 378849 3...

output:

1998000
232 671 1 671
232 407 1 407
232 40 1 40
232 554 1 554
232 995 1 995
232 577 1 577
232 486 1 486
232 431 1 431
232 854 1 854
232 660 1 660
232 560 1 560
232 457 1 457
232 740 1 740
232 268 1 268
232 382 1 382
232 483 1 483
232 11 1 11
232 295 1 295
232 329 1 329
232 504 1 504
232 867 1 867
23...

result:

ok Accepted.

Test #17:

score: 0
Accepted
time: 361ms
memory: 49540kb

input:

1000
383379 383297 383978 383304 383827 383736 383312 383974 383292 383005 383064 383173 383632 383665 383126 383171 383186 383209 383497 383241 383135 383308 383430 383202 383797 383628 383167 383714 383592 383577 383533 383967 383080 383764 383899 383763 383437 383205 383683 383953 383916 383039 3...

output:

1998000
671 232 1 232
671 654 1 654
671 607 1 607
671 299 1 299
671 10 1 10
671 653 1 653
671 344 1 344
671 830 1 830
671 347 1 347
671 702 1 702
671 125 1 125
671 216 1 216
671 190 1 190
671 780 1 780
671 339 1 339
671 501 1 501
671 362 1 362
671 670 1 670
671 644 1 644
671 912 1 912
671 242 1 242
...

result:

ok Accepted.

Test #18:

score: 0
Accepted
time: 231ms
memory: 33144kb

input:

1000
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 101 1...

output:

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

result:

ok Accepted.

Test #19:

score: 0
Accepted
time: 215ms
memory: 31836kb

input:

1000
1000000 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...

output:

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

result:

ok Accepted.

Test #20:

score: 0
Accepted
time: 294ms
memory: 48512kb

input:

1000
2 1002 2002 3002 4002 5002 6002 7002 8002 9002 10002 11002 12002 13002 14002 15002 16002 17002 18002 19002 20002 21002 22002 23002 24002 25002 26002 27002 28002 29002 30002 31002 32002 33002 34002 35002 36002 37002 38002 39002 40002 41002 42002 43002 44002 45002 46002 47002 48002 49002 50002 51...

output:

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

result:

ok Accepted.

Test #21:

score: 0
Accepted
time: 365ms
memory: 49588kb

input:

1000
383379 383297 383978 383304 383827 383736 383312 383974 383292 383005 383064 383173 383632 383665 383126 383171 383186 383209 383497 383241 383135 383308 383430 383202 383797 383628 383167 383714 383592 383577 383533 383967 383080 383764 383899 383763 383437 383205 383683 383953 383916 383039 3...

output:

1997999
671 232 1 232
671 654 1 654
671 607 1 607
671 299 1 299
671 10 1 10
671 653 1 653
671 344 1 344
671 830 1 830
671 347 1 347
671 702 1 702
671 125 1 125
671 216 1 216
671 190 1 190
671 780 1 780
671 339 1 339
671 501 1 501
671 362 1 362
671 670 1 670
671 644 1 644
671 912 1 912
671 242 1 242
...

result:

ok Accepted.

Test #22:

score: 0
Accepted
time: 381ms
memory: 48412kb

input:

1000
383379 383297 383978 383304 383827 383736 383312 383974 383292 383005 383064 383173 383632 383665 383126 383171 383186 383209 383497 383241 383135 383308 383430 383202 383797 383628 383167 383714 383592 383577 383533 383967 383080 383764 383899 383763 383437 383205 383683 383953 383916 383039 3...

output:

1997998
671 232 1 232
671 654 1 654
671 607 1 607
671 299 1 299
671 10 1 10
671 653 1 653
671 344 1 344
671 830 1 830
671 347 1 347
671 702 1 702
671 125 1 125
671 216 1 216
671 190 1 190
671 780 1 780
671 339 1 339
671 501 1 501
671 362 1 362
671 670 1 670
671 644 1 644
671 912 1 912
671 242 1 242
...

result:

ok Accepted.

Test #23:

score: 0
Accepted
time: 405ms
memory: 49460kb

input:

1000
921156 164917 876716 346601 859849 128010 597453 517820 153764 816228 42630 968115 720674 725887 873481 472730 923921 922689 526667 758819 770342 216266 971717 759305 966908 301482 74863 561426 880217 783710 560336 923860 491882 553154 530791 476240 818078 877946 148671 206130 898917 24153 5407...

output:

1998000
149 671 1 671
74 407 1 407
42 40 1 40
296 554 1 554
873 995 1 995
66 577 1 577
523 486 1 486
353 431 1 431
240 854 1 854
303 660 1 660
517 560 1 560
460 457 1 457
897 740 1 740
563 268 1 268
148 382 1 382
772 483 1 483
79 11 1 11
415 295 1 295
458 329 1 329
125 504 1 504
484 867 1 867
339 50...

result:

ok Accepted.

Test #24:

score: 0
Accepted
time: 371ms
memory: 47932kb

input:

1000
383379 383297 383978 383304 383827 383736 383312 383974 383292 383005 383064 383173 383632 383665 383126 383171 383186 383209 383497 383241 383135 383308 383430 383202 383797 383628 383167 383714 383592 383577 383533 383967 383080 383764 383899 383763 383437 383205 383683 383953 383916 383039 3...

output:

1997997
671 232 1 232
671 654 1 654
671 607 1 607
671 299 1 299
671 10 1 10
671 653 1 653
671 344 1 344
671 830 1 830
671 347 1 347
671 702 1 702
671 125 1 125
671 216 1 216
671 190 1 190
671 780 1 780
671 339 1 339
671 501 1 501
671 362 1 362
671 670 1 670
671 644 1 644
671 912 1 912
671 242 1 242
...

result:

ok Accepted.

Test #25:

score: 0
Accepted
time: 363ms
memory: 48428kb

input:

1000
765923 765649 765437 765697 765568 765166 765024 765681 765965 765556 765185 765781 765602 765901 765351 765204 765910 765739 765588 765769 765129 765812 765968 765116 765034 765868 765858 765150 765281 765770 765544 765940 765937 765712 765478 765018 765443 765380 765400 765094 765499 765591 7...

output:

1997996
807 105 1 105
807 607 1 607
807 273 1 273
807 679 1 679
807 476 1 476
807 623 1 623
807 420 1 420
807 187 1 187
807 326 1 326
807 695 1 695
807 449 1 449
807 359 1 359
807 485 1 485
807 763 1 763
807 953 1 953
807 466 1 466
807 961 1 961
807 36 1 36
807 502 1 502
807 744 1 744
807 48 1 48
80...

result:

ok Accepted.

Test #26:

score: 0
Accepted
time: 375ms
memory: 48168kb

input:

1000
546593 546244 546560 546842 546335 546503 546719 546740 546296 546648 546372 546145 546975 546991 546749 546261 546863 546655 546224 546054 546895 546155 546989 546986 546102 546059 546004 546040 546408 546083 546748 546384 546206 546405 546908 546565 546431 546822 546783 546641 546418 546915 5...

output:

1997995
419 861 1 861
419 438 1 438
419 212 1 212
419 27 1 27
419 264 1 264
419 674 1 674
419 884 1 884
419 195 1 195
419 290 1 290
419 186 1 186
419 723 1 723
419 76 1 76
419 917 1 917
419 315 1 315
419 493 1 493
419 835 1 835
419 352 1 352
419 266 1 266
419 92 1 92
419 742 1 742
419 385 1 385
419 ...

result:

ok Accepted.

Test #27:

score: 0
Accepted
time: 353ms
memory: 48648kb

input:

1000
245814 245896 245217 245160 245517 245789 245688 245243 245869 245548 245479 245226 245868 245331 245543 245629 245529 245780 245057 245567 245406 245454 245206 245415 245139 245416 245382 245039 245937 245267 245038 245787 245859 245892 245597 245536 245376 245846 245275 245307 245485 245430 2...

output:

1997994
13 297 1 297
13 591 1 591
13 971 1 971
13 841 1 841
13 148 1 148
13 860 1 860
13 94 1 94
13 835 1 835
13 834 1 834
13 365 1 365
13 604 1 604
13 323 1 323
13 339 1 339
13 413 1 413
13 458 1 458
13 907 1 907
13 246 1 246
13 329 1 329
13 205 1 205
13 784 1 784
13 484 1 484
13 630 1 630
13 979 1...

result:

ok Accepted.

Test #28:

score: 0
Accepted
time: 383ms
memory: 48972kb

input:

1000
61557 61538 61992 61418 61459 61224 61009 61367 61604 61243 61423 61873 61774 61436 61466 61011 61671 61260 61308 61856 61622 61332 61984 61422 61645 61548 61419 61435 61165 61664 61340 61520 61182 61649 61043 61874 61024 61307 61797 61837 61795 61802 61900 61388 61836 61144 61064 61351 61740 6...

output:

1997993
963 219 1 219
963 961 1 961
963 126 1 126
963 482 1 482
963 105 1 105
963 481 1 481
963 835 1 835
963 62 1 62
963 7 1 7
963 515 1 515
963 16 1 16
963 556 1 556
963 986 1 986
963 641 1 641
963 764 1 764
963 669 1 669
963 224 1 224
963 469 1 469
963 86 1 86
963 119 1 119
963 768 1 768
963 308 ...

result:

ok Accepted.

Test #29:

score: 0
Accepted
time: 390ms
memory: 48108kb

input:

1000
996685 996990 996192 996880 996864 996813 996152 996416 996490 996815 996429 996877 996274 996981 996865 996133 996918 996203 996594 996222 996849 996243 996832 996684 996586 996704 996703 996007 996097 996147 996190 996188 996965 996057 996076 996632 996229 996174 996678 996602 996963 996206 9...

output:

1997992
852 642 1 642
852 891 1 891
852 574 1 574
852 593 1 593
852 898 1 898
852 230 1 230
852 28 1 28
852 543 1 543
852 163 1 163
852 844 1 844
852 329 1 329
852 989 1 989
852 587 1 587
852 599 1 599
852 463 1 463
852 741 1 741
852 656 1 656
852 400 1 400
852 508 1 508
852 566 1 566
852 65 1 65
85...

result:

ok Accepted.

Test #30:

score: 0
Accepted
time: 388ms
memory: 47952kb

input:

1000
335743 335130 335163 335806 335670 335141 335943 335395 335599 335515 335230 335687 335598 335233 335243 335478 335454 335447 335795 335610 335790 335298 335480 335392 335965 335237 335193 335913 335889 335097 335414 335323 335458 335049 335682 335178 335361 335117 335509 335405 335155 335643 3...

output:

1997991
792 279 1 279
792 47 1 47
792 814 1 814
792 827 1 827
792 310 1 310
792 699 1 699
792 148 1 148
792 135 1 135
792 296 1 296
792 88 1 88
792 299 1 299
792 811 1 811
792 381 1 381
792 346 1 346
792 893 1 893
792 499 1 499
792 211 1 211
792 466 1 466
792 801 1 801
792 537 1 537
792 407 1 407
79...

result:

ok Accepted.

Test #31:

score: 0
Accepted
time: 358ms
memory: 48624kb

input:

1000
572459 572682 572811 572715 572911 572627 572137 572476 572893 572536 572732 572728 572092 572885 572750 572853 572867 572143 572883 572626 572469 572850 572378 572238 572513 572663 572537 572514 572823 572533 572983 572488 572518 572970 572275 572685 572709 572915 572145 572721 572636 572611 5...

output:

1997999
518 763 1 763
518 769 1 769
518 626 1 626
518 568 1 568
518 512 1 512
518 818 1 818
518 186 1 186
518 86 1 86
518 955 1 955
518 60 1 60
518 377 1 377
518 339 1 339
518 960 1 960
518 945 1 945
518 431 1 431
518 381 1 381
518 897 1 897
518 663 1 663
518 120 1 120
518 667 1 667
518 500 1 500
51...

result:

ok Accepted.

Test #32:

score: 0
Accepted
time: 393ms
memory: 48732kb

input:

1000
560571 560121 560859 560154 560235 560862 560729 560218 560048 560834 560772 560351 560458 560413 560960 560089 560411 560068 560593 560671 560150 560369 560826 560330 560064 560013 560594 560409 560775 560077 560617 560237 560763 560554 560848 560869 560138 560454 560249 560083 560661 560450 5...

output:

1997998
987 473 1 473
987 854 1 854
987 901 1 901
987 970 1 970
987 692 1 692
987 320 1 320
987 924 1 924
987 414 1 414
987 509 1 509
987 49 1 49
987 353 1 353
987 305 1 305
987 26 1 26
987 839 1 839
987 571 1 571
987 634 1 634
987 72 1 72
987 281 1 281
987 319 1 319
987 175 1 175
987 374 1 374
987 ...

result:

ok Accepted.

Test #33:

score: 0
Accepted
time: 382ms
memory: 48704kb

input:

1000
598160 598843 598010 598357 598885 598475 598861 598480 598441 598457 598228 598823 598020 598523 598864 598088 598474 598544 598151 598873 598535 598409 598538 598665 598103 598101 598403 598871 598892 598851 598816 598219 598597 598989 598844 598614 598098 598332 598852 598251 598909 598473 5...

output:

1997997
52 694 1 694
52 865 1 865
52 927 1 927
52 917 1 917
52 403 1 403
52 809 1 809
52 179 1 179
52 951 1 951
52 611 1 611
52 3 1 3
52 713 1 713
52 575 1 575
52 153 1 153
52 826 1 826
52 238 1 238
52 964 1 964
52 697 1 697
52 87 1 87
52 807 1 807
52 13 1 13
52 548 1 548
52 969 1 969
52 792 1 792
5...

result:

ok Accepted.

Test #34:

score: 0
Accepted
time: 404ms
memory: 49728kb

input:

1000
921156 164917 876716 346601 859849 128010 597453 517820 153764 816228 42630 968115 720674 725887 873481 472730 923921 922689 526667 758819 770342 216266 971717 759305 966908 301482 74863 561426 880217 783710 560336 923860 491882 553154 530791 476240 818078 877946 148671 206130 898917 24153 5407...

output:

1998000
149 671 1 671
74 407 1 407
42 40 1 40
296 554 1 554
873 995 1 995
66 577 1 577
523 486 1 486
353 431 1 431
240 854 1 854
303 660 1 660
517 560 1 560
460 457 1 457
897 740 1 740
563 268 1 268
148 382 1 382
772 483 1 483
79 11 1 11
415 295 1 295
458 329 1 329
125 504 1 504
484 867 1 867
339 50...

result:

ok Accepted.

Test #35:

score: 0
Accepted
time: 404ms
memory: 48240kb

input:

1000
556261 556653 556726 556247 556206 556107 556120 556211 556540 556334 556145 556239 556097 556734 556476 556244 556401 556470 556005 556884 556699 556936 556696 556587 556602 556264 556919 556458 556555 556159 556003 556778 556209 556631 556009 556558 556478 556396 556771 556550 556348 556687 5...

output:

1997996
934 407 1 407
934 594 1 594
934 31 1 31
934 462 1 462
934 19 1 19
934 982 1 982
934 443 1 443
934 68 1 68
934 35 1 35
934 182 1 182
934 415 1 415
934 834 1 834
934 81 1 81
934 927 1 927
934 481 1 481
934 395 1 395
934 729 1 729
934 917 1 917
934 426 1 426
934 404 1 404
934 660 1 660
934 206 ...

result:

ok Accepted.

Test #36:

score: 0
Accepted
time: 376ms
memory: 49668kb

input:

1000
95449 95943 95602 95263 95644 95061 95279 95813 95740 95242 95951 95803 95352 95696 95234 95841 95645 95953 95156 95923 95509 95368 95764 95533 95364 95265 95689 95850 95430 95978 95746 95556 95679 95587 95250 95799 95520 95779 95539 95333 95722 95889 95989 95670 95899 95654 95003 95920 95150 9...

output:

1997900
362 488 362 739
362 739 1 739
362 322 362 488
362 488 1 488
362 517 362 322
362 322 1 322
362 725 362 517
362 517 1 517
362 356 362 725
362 725 1 725
362 577 362 356
362 356 1 356
362 842 362 577
362 577 1 577
362 830 362 842
362 842 1 842
362 952 362 830
362 830 1 830
362 525 362 952
362 95...

result:

ok Accepted.

Test #37:

score: 0
Accepted
time: 390ms
memory: 48240kb

input:

1000
957448 957161 957642 957882 957356 957099 957743 957390 957589 957676 957377 957868 957239 957063 957961 957996 957341 957324 957673 957716 957912 957824 957633 957343 957611 957656 957627 957342 957022 957152 957068 957859 957411 957388 957646 957809 957540 957067 957208 957112 957751 957015 9...

output:

1997800
723 931 723 930
723 930 1 930
723 875 723 931
723 931 1 931
723 524 723 875
723 875 1 875
723 974 723 524
723 524 1 524
723 312 723 974
723 974 1 974
723 66 723 312
723 312 1 312
723 98 723 66
723 66 1 66
723 309 723 98
723 98 1 98
723 936 723 309
723 309 1 309
723 551 723 936
723 936 1 936
...

result:

ok Accepted.

Test #38:

score: 0
Accepted
time: 365ms
memory: 48788kb

input:

1000
60816 60166 60381 60643 60789 60512 60070 60017 60202 60063 60104 60853 60368 60399 60504 60254 60373 60980 60116 60003 60493 60222 60187 60676 60314 60798 60554 60653 60207 60278 60217 60501 60507 60074 60110 60686 60487 60647 60065 60426 60893 60161 60047 60359 60878 60821 60127 60077 60423 6...

output:

1997586
922 512 922 316
922 316 1 316
922 263 922 642
922 642 1 642
922 486 922 923
922 923 1 923
922 6 922 512
922 512 1 512
922 291 922 263
922 263 1 263
922 800 922 486
922 486 1 486
922 391 922 6
922 6 1 6
922 919 922 291
922 291 1 291
922 907 922 391
922 391 1 391
922 477 922 919
922 919 1 919
...

result:

ok Accepted.

Test #39:

score: 0
Accepted
time: 371ms
memory: 48620kb

input:

1000
24647 24015 24359 24034 24755 24059 24886 24037 24547 24668 24108 24396 24575 24065 24243 24267 24289 24914 24299 24479 25000 24348 24020 24984 24472 24176 24062 24453 24915 24561 24229 24136 24463 24943 24551 24741 24569 24959 24500 24505 24281 24493 24251 24358 24385 24439 24067 24095 24345 2...

output:

1997164
315 251 315 577
315 577 1 577
315 43 315 251
315 251 1 251
315 865 315 43
315 43 1 43
315 204 315 865
315 865 1 865
315 701 315 204
315 204 1 204
315 626 315 701
315 701 1 701
315 145 315 626
315 626 1 626
315 979 315 145
315 145 1 145
315 957 315 979
315 979 1 979
315 636 315 957
315 957 1 ...

result:

ok Accepted.

Test #40:

score: 0
Accepted
time: 423ms
memory: 48192kb

input:

1000
331539 331151 331975 331601 331812 331879 331223 331408 331843 331333 331996 331947 331912 331815 331770 331659 331282 331390 331549 331329 331262 331138 331003 331714 331529 331146 331167 331790 331598 331981 331787 331425 331637 331654 331431 331968 331621 331074 331448 331391 331832 331645 3...

output:

1996528
970 330 970 44
970 44 1 44
970 782 970 758
970 758 1 758
970 171 970 772
970 772 1 772
970 708 970 330
970 330 1 330
970 1000 970 782
970 782 1 782
970 289 970 171
970 171 1 171
970 61 970 708
970 708 1 708
970 960 970 1000
970 1000 1 1000
970 836 970 289
970 289 1 289
970 336 970 61
970 61 ...

result:

ok Accepted.

Test #41:

score: 0
Accepted
time: 398ms
memory: 49812kb

input:

1000
545268 545435 545452 545916 545410 545648 545938 545405 545776 545017 545588 545887 545053 545614 545579 545130 545502 545057 545581 545421 545088 545815 545276 545688 545429 545947 545690 545522 545496 545723 724634 545868 545575 545876 545303 545367 545180 545464 545501 545274 545059 545081 5...

output:

1995702
690 711 690 146
690 146 1 146
690 808 690 517
690 517 1 517
690 693 690 612
690 612 1 612
690 897 690 775
690 775 1 775
690 252 690 945
690 945 1 945
690 984 690 711
690 711 1 711
690 216 690 808
690 808 1 808
690 553 690 693
690 693 1 693
690 143 690 897
690 897 1 897
690 362 690 252
690 25...

result:

ok Accepted.

Test #42:

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

input:

1000
854919 854197 854949 854159 854732 854190 854561 854846 854266 854264 854736 854984 854714 854367 854665 854105 854717 854883 854698 854037 854543 854139 854413 854472 854876 854279 854570 854483 854990 854492 854576 854648 854049 854811 854660 854605 854184 854112 854553 854093 854103 854563 8...

output:

1994600
845 562 845 106
845 106 1 106
845 359 845 115
845 115 1 115
845 602 845 265
845 265 1 265
845 789 845 275
845 275 1 275
845 574 845 317
845 317 1 317
845 863 845 320
845 320 1 320
845 162 845 399
845 399 1 399
845 763 845 410
845 410 1 410
845 765 845 460
845 460 1 460
845 432 845 497
845 49...

result:

ok Accepted.

Test #43:

score: 0
Accepted
time: 410ms
memory: 48812kb

input:

1000
591079 591433 591985 591891 591534 591576 591774 591351 591039 591650 591852 591741 591792 591260 591776 591878 595243 591947 591975 591071 591643 591110 591680 591601 591310 591956 591610 591525 591256 591457 591778 591400 591319 591584 591882 591365 591143 591825 591660 677358 591608 591511 5...

output:

1993818
87 798 87 74
87 74 1 74
87 126 87 146
87 146 1 146
87 125 87 169
87 169 1 169
87 745 87 323
87 323 1 323
87 841 87 397
87 397 1 397
87 582 87 425
87 425 1 425
87 772 87 426
87 426 1 426
87 192 87 440
87 440 1 440
87 652 87 505
87 505 1 505
87 42 87 511
87 511 1 511
87 337 87 567
87 567 1 567...

result:

ok Accepted.

Test #44:

score: 0
Accepted
time: 400ms
memory: 49156kb

input:

1000
178582 178716 115203 178547 178946 178469 178602 178019 178344 921655 178082 178169 178504 178893 178027 178441 433666 178446 341788 178095 178520 178963 178952 178707 178696 178680 178722 178163 178231 178065 178635 178869 178703 178492 178149 178207 178221 178724 178498 178821 178763 178455 1...

output:

1992816
768 19 768 7
768 7 1 7
768 649 768 25
768 25 1 25
768 900 768 45
768 45 1 45
768 737 768 77
768 77 1 77
768 123 768 105
768 105 1 105
768 244 768 121
768 121 1 121
768 540 768 161
768 161 1 161
768 104 768 168
768 168 1 168
768 953 768 223
768 223 1 223
768 661 768 271
768 271 1 271
768 309 ...

result:

ok Accepted.

Test #45:

score: 0
Accepted
time: 415ms
memory: 49016kb

input:

1000
921156 164917 876716 346601 859849 128010 597453 517820 153764 816228 42630 968115 720674 725887 873481 472730 923921 922689 526667 758819 770342 216266 971717 759305 966908 301482 74863 561426 880217 783710 560336 923860 491882 553154 530791 476240 818078 877946 148671 206130 898917 24153 5407...

output:

1991005
149 671 1 671
74 407 1 407
42 40 1 40
296 554 1 554
873 995 1 995
66 577 1 577
523 486 1 486
353 431 1 431
240 854 1 854
303 660 1 660
517 560 1 560
460 457 1 457
897 740 1 740
563 268 1 268
148 382 1 382
772 483 1 483
79 11 1 11
415 295 1 295
458 329 1 329
125 504 1 504
484 867 1 867
339 50...

result:

ok Accepted.

Test #46:

score: 0
Accepted
time: 415ms
memory: 48860kb

input:

1000
471689 471319 471406 471740 471640 471038 471566 471232 471127 471889 471205 471125 471429 471645 471835 471247 471929 471750 471151 471197 471897 471767 471891 471785 471552 471718 471628 471202 471399 471943 471727 2874 471236 471560 471241 471224 471915 471323 471636 471624 19811 471649 4715...

output:

1991956
220 662 220 26
220 26 1 26
688 688 688 34
688 34 1 34
688 6 688 38
688 38 1 38
688 795 688 55
688 55 1 55
688 400 688 58
688 58 1 58
688 96 688 86
688 86 1 86
688 193 688 87
688 87 1 87
688 409 688 88
688 88 1 88
688 468 688 94
688 94 1 94
688 846 688 100
688 100 1 100
688 12 688 125
688 125...

result:

ok Accepted.

Test #47:

score: 0
Accepted
time: 424ms
memory: 48544kb

input:

1000
921156 164917 876716 346601 859849 128010 597453 517820 153764 816228 42630 968115 720674 725887 873481 472730 923921 922689 526667 758819 770342 216266 971717 759305 966908 301482 74863 561426 880217 783710 560336 923860 491882 553154 530791 476240 818078 877946 148671 206130 898917 24153 5407...

output:

1990662
149 671 1 671
74 407 1 407
42 40 1 40
296 554 1 554
873 995 1 995
66 577 1 577
523 486 1 486
353 431 1 431
240 854 1 854
303 660 1 660
517 560 1 560
460 457 1 457
897 740 1 740
563 268 1 268
148 382 1 382
772 483 1 483
79 11 1 11
415 295 1 295
458 329 1 329
125 504 1 504
484 867 1 867
339 50...

result:

ok Accepted.

Test #48:

score: 0
Accepted
time: 406ms
memory: 48744kb

input:

1000
921156 164917 876716 346601 859849 128010 597453 517820 153764 816228 42630 968115 720674 725887 873481 472730 923921 922689 526667 758819 770342 216266 971717 759305 966908 301482 74863 561426 880217 783710 560336 923860 491882 553154 530791 476240 818078 877946 148671 206130 898917 24153 5407...

output:

1990096
149 671 1 671
74 407 1 407
42 40 1 40
296 554 1 554
873 995 1 995
66 577 1 577
523 486 1 486
353 431 1 431
240 854 1 854
303 660 1 660
517 560 1 560
460 457 1 457
897 740 1 740
563 268 1 268
148 382 1 382
772 483 1 483
79 11 1 11
415 295 1 295
458 329 1 329
125 504 1 504
484 867 1 867
339 50...

result:

ok Accepted.

Test #49:

score: 0
Accepted
time: 416ms
memory: 49208kb

input:

1000
921156 164917 876716 346601 859849 128010 597453 517820 153764 816228 42630 968115 720674 725887 873481 472730 923921 922689 526667 758819 770342 216266 971717 759305 966908 301482 74863 561426 880217 783710 560336 923860 491882 553154 530791 476240 818078 877946 148671 206130 898917 24153 5407...

output:

1990116
149 671 1 671
74 407 1 407
42 40 1 40
296 554 1 554
873 995 1 995
66 577 1 577
523 486 1 486
353 431 1 431
240 854 1 854
303 660 1 660
517 560 1 560
460 457 1 457
897 740 1 740
563 268 1 268
148 382 1 382
772 483 1 483
79 11 1 11
415 295 1 295
458 329 1 329
125 504 1 504
484 867 1 867
339 50...

result:

ok Accepted.

Test #50:

score: 0
Accepted
time: 418ms
memory: 48116kb

input:

1000
921156 164917 876716 346601 859849 128010 597453 517820 153764 816228 42630 968115 720674 725887 873481 472730 923921 922689 526667 758819 770342 216266 971717 759305 966908 301482 74863 561426 880217 783710 560336 923860 491882 553154 530791 476240 818078 877946 148671 206130 898917 24153 5407...

output:

1990066
149 671 1 671
74 407 1 407
42 40 1 40
296 554 1 554
873 995 1 995
66 577 1 577
523 486 1 486
353 431 1 431
240 854 1 854
303 660 1 660
517 560 1 560
460 457 1 457
897 740 1 740
563 268 1 268
148 382 1 382
772 483 1 483
79 11 1 11
415 295 1 295
458 329 1 329
125 504 1 504
484 867 1 867
339 50...

result:

ok Accepted.