QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#200409#7349. UFO RectanglesSolitaryDream#AC ✓55ms49956kbC++203.8kb2023-10-04 16:53:362023-10-04 16:53:38

Judging History

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

  • [2023-10-04 16:53:38]
  • 评测
  • 测评结果:AC
  • 用时:55ms
  • 内存:49956kb
  • [2023-10-04 16:53:36]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
const int N = 2010;
int n, m;
char mp[N][N];
int ru[N][N], rd[N][N];
// int sm[N][N];
inline int Ask(int x, int y, int u, int v) {
    // return sm[u][v] - sm[x - 1][v] - sm[u][y - 1] + sm[x - 1][y - 1];
    int ans = 0;
    for (int i = x; i <= u; ++i)
        for (int j = y; j <= v; ++j)
            ans += (mp[i][j] == 'X');
    return ans;
}
inline bool Check(int x, int y, int u, int v) {
    // return Ask(x, y, u, v) == (u - x + 1) * (v - y + 1);
    int l_len = 3, r_len = 3;
    for (int i = x; i <= u; ++i) {
        if (mp[i][y] != 'X') return 0;
        if (mp[i][y - 1] == 'X') ++l_len;
        else { 
            if (l_len >= 1 && l_len <= 2) return 0;
            l_len = 0;
        }
        if (mp[i][y + 1] == 'X') ++r_len;
        else { 
            if (r_len >= 1 && r_len <= 2) return 0;
            r_len = 0;
        }
    }
    return 1;
}
vector<vector<int>> ans;
inline void Push(int x, int y, int u, int v) {
    // printf("Push %d %d %d %d\n", x, y, u, v);
    ans.push_back({x, y, u, v});
    for (int i = x; i <= u; ++i) mp[i][y] = mp[i][v] = '.';
    for (int i = y; i <= v; ++i) mp[x][i] = mp[u][i] = '.';
    // for (int i = 1; i <= n; ++i) puts(mp[i] + 1);
}
inline bool IsCorner(int i, int j, int d) {
    int d2 = (d + 1) & 3;
    if (mp[i][j] != 'X') return 0;
    if (mp[i + dx[d]][j + dy[d]] != 'X') return 0;
    if (mp[i + dx[d2]][j + dy[d2]] != 'X') return 0;
    if (mp[i + dx[d] + dx[d2]][j + dy[d] + dy[d2]] != '.') return 0;
    return 1;
}
int main() {
    // n = 2000 / 3 * 3, m = n;
    // // cerr << n * m / 9 << endl;
    // for(int i = 1; i <= n; i += 1)
    //     for(int j = 1; j <= m; j += 1)
    //         mp[i][j] = (i % 3 == 2 && j % 3 == 2 ? '.' : 'X');
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%s", mp[i] + 1);
    }
    // for (int i = 1; i <= n; ++i)
    //     for (int j = 1; j <= m; ++j) {
    //         // sm[i][j] = sm[i - 1][j] + sm[i][j - 1] - sm[i - 1][j - 1];
    //         if (mp[i][j] == 'X') {
    //             bool flag = 1;
    //             // for (int d = 0; d < 4; ++d) if (IsCorner(i, j, d)) flag = 0;
    //             sm[i][j] += flag;
    //         }
    //     }
    for (int i = 1; i <= n; ++i) {
        ru[i][m + 1] = m + 1;
        rd[i][m + 1] = m + 1;
        for (int j = m; j; --j) {
            ru[i][j] = ru[i][j + 1];
            rd[i][j] = rd[i][j + 1];
            if (IsCorner(i, j, 2)) ru[i][j] = j;
            if (IsCorner(i, j, 3)) rd[i][j] = j;
        }
    }
    for (int j = 1; j <= m; ++j)
        for (int i = 1; i <= n; ++i) if (mp[i][j] == 'X') {
            for (int k = i + 2; k <= n; ++k) if (IsCorner(k, j, 0)) {
                if (Ask(k, j, k + 2, j + 1) == 6) continue;
                int ri = ru[i][j + 1], rk = rd[k][j + 1];
                while (1) {
                    if (ri < rk) ri = ru[i][ri + 1];
                    else if (rk < ri) rk = rd[k][rk + 1];
                    else {
                        if (Check(i, ri, k, rk)) break;
                        ri = ru[i][ri + 1];
                        rk = rd[k][rk + 1];
                    }
                }
                Push(i, j, k, ri);
                // p
                // return 0;
                break;
            }
        }
    printf("%d\n", (int)ans.size());
    for (auto v : ans) printf("%d %d %d %d\n", v[0], v[1], v[2], v[3]);
    return 0;
}

/*
10 10
..........
XXXXXXXXXX
X...XXXX.X
X...X..X.X
X...XXXX.X
X.XXX.XXXX
X.X.X.X.XX
X.X.X.XXXX
X.XXX....X
XXXXXXXXXX

10 10
..........
XXXXXXXXXX
X........X
XXXX.....X
XX.X.....X
XXXX..XXXX
X.....X.XX
X.....XXXX
X........X
XXXXXXXXXX

5 6
XXX...
X.X...
XXXXXX
...X.X
...XXX

*/

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 7832kb

input:

3 3
XXX
X.X
XXX

output:

1
1 1 3 3

result:

ok answer is correct. 1 frames found

Test #2:

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

input:

6 7
XXXXXXX
X.XX..X
XXXXXXX
XXXXXXX
X.XX..X
XXXXXXX

output:

4
1 1 3 3
4 1 6 3
1 4 3 7
4 4 6 7

result:

ok answer is correct. 4 frames found

Test #3:

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

input:

10 10
..........
XXXXXXXXXX
X..XXXX..X
X..X..X..X
X..XXXX..X
X...XXXX.X
X...X..X.X
X...X..X.X
X...XXXX.X
XXXXXXXXXX

output:

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

result:

ok answer is correct. 3 frames found

Test #4:

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

input:

7 10
...XXX....
...X.XXXX.
...XXXX.X.
..XXX.XXX.
..X.XXXX..
..XXXX.X..
.....XXX..

output:

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

result:

ok answer is correct. 4 frames found

Test #5:

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

input:

10 10
..........
XXXXXXXXXX
X..XXXX..X
X..X..X..X
X..XXXX..X
XXXXXXXX.X
XX.XX..X.X
XXXXX..X.X
X...XXXX.X
XXXXXXXXXX

output:

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

result:

ok answer is correct. 4 frames found

Test #6:

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

input:

3 3
...
...
...

output:

0

result:

ok answer is correct. 0 frames found

Test #7:

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

input:

100 100
....................................................................................................
.............................................XXXXXXXXXXXXX..........................................
.............................................X...........X...................................

output:

53
74 1 96 4
41 2 49 28
54 2 58 45
43 4 45 7
46 7 48 9
79 7 88 13
62 9 74 90
82 9 86 12
42 10 46 19
69 11 73 70
20 14 24 35
63 14 67 82
9 16 13 83
44 20 46 24
43 25 45 27
89 25 94 51
90 27 92 30
91 31 93 48
38 33 51 42
44 34 49 38
39 35 43 38
20 38 36 79
42 39 49 41
79 39 88 93
26 40 28 46
29 41 32 ...

result:

ok answer is correct. 53 frames found

Test #8:

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

input:

200 200
..................................................XXXXXXXXXXXXXXXXXX....................................................................................................................................
..................................................X................X...............XXXXXXXX...

output:

163
62 4 76 45
64 8 75 12
84 12 108 16
25 13 33 36
69 14 75 40
64 15 67 32
27 16 31 25
71 16 74 19
139 19 161 21
70 23 73 33
174 25 196 170
26 27 29 29
113 27 115 42
178 27 182 30
185 29 190 94
28 30 32 34
186 31 188 33
64 33 68 39
176 33 183 61
70 35 73 37
161 35 169 38
177 35 179 45
186 37 188 52
...

result:

ok answer is correct. 163 frames found

Test #9:

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

input:

300 300
.......................................................................................................................................................................................................................................................................................................

output:

304
130 7 261 10
158 11 262 23
195 12 222 21
231 12 237 20
9 13 83 23
201 13 204 15
206 13 209 15
224 13 226 15
233 13 235 15
12 14 22 19
40 14 56 18
166 14 179 16
191 14 194 22
215 14 218 16
15 15 17 17
32 15 34 18
63 15 67 22
75 15 79 22
184 15 187 17
238 15 247 21
18 16 20 18
68 16 70 21
198 16 2...

result:

ok answer is correct. 304 frames found

Test #10:

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

input:

400 400
.......................................................................................................................................................................................................................................................................................................

output:

427
41 7 291 47
48 8 270 30
169 10 265 12
281 13 289 27
62 14 130 17
178 14 205 16
283 14 285 18
42 16 45 30
226 17 251 22
50 18 205 21
228 18 237 20
238 18 247 20
284 19 287 21
70 22 78 29
79 22 112 24
153 22 164 27
284 22 286 25
72 23 76 25
156 23 161 25
146 24 150 26
212 24 236 29
228 25 232 27
7...

result:

ok answer is correct. 427 frames found

Test #11:

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

input:

500 500
.......................................................................................................................................................................................................................................................................................................

output:

619
195 23 261 26
94 24 139 61
118 26 128 28
108 27 113 30
131 30 138 35
97 31 115 33
122 31 130 38
133 31 135 33
118 34 121 37
123 34 128 36
136 37 138 51
107 38 113 55
132 40 134 54
353 40 467 312
334 41 349 82
109 42 111 51
339 42 345 50
98 43 104 57
123 43 131 47
340 44 342 46
335 45 337 55
99 4...

result:

ok answer is correct. 619 frames found

Test #12:

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

input:

600 600
.......................................................................................................................................................................................................................................................................................................

output:

736
572 5 589 45
575 7 578 9
579 8 586 12
242 13 268 76
250 14 260 16
263 14 265 57
578 14 580 17
243 18 260 20
573 18 583 22
585 23 587 32
245 24 261 35
574 24 576 29
250 25 252 27
577 25 583 28
257 27 259 32
246 30 255 32
574 30 576 41
579 30 582 34
586 37 588 40
243 38 246 56
248 39 255 52
579 40...

result:

ok answer is correct. 736 frames found

Test #13:

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

input:

700 700
.......................................................................................................................................................................................................................................................................................................

output:

940
439 12 566 34
472 13 477 15
479 13 490 16
497 15 500 24
501 16 525 18
526 17 532 20
455 18 491 32
538 18 565 23
463 19 481 22
443 20 449 25
542 20 563 22
527 21 530 23
445 22 447 24
483 22 485 25
456 23 463 27
470 24 475 27
547 24 550 26
514 25 535 31
480 26 482 28
485 26 488 31
520 26 526 29
44...

result:

ok answer is correct. 940 frames found

Test #14:

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

input:

800 800
.......................................................................................................................................................................................................................................................................................................

output:

1107
655 8 666 265
658 28 662 59
94 49 651 198
327 53 597 56
663 57 665 70
485 58 554 63
354 59 443 63
490 59 494 61
498 59 501 61
503 59 533 61
535 59 550 61
301 66 635 82
158 68 299 189
394 68 442 71
274 69 285 76
521 69 575 72
277 70 279 73
472 70 505 74
280 71 283 74
316 71 386 81
599 71 630 74
...

result:

ok answer is correct. 1107 frames found

Test #15:

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

input:

900 900
.......................................................................................................................................................................................................................................................................................................

output:

1171
203 7 425 28
277 8 306 11
329 8 331 16
215 9 219 12
231 9 239 17
352 10 385 12
417 10 421 17
232 12 234 14
235 12 237 15
764 12 769 262
262 13 315 17
344 14 395 24
399 14 405 19
350 15 360 17
369 15 372 17
378 15 386 17
249 16 256 18
401 16 403 18
345 18 359 21
367 18 390 20
765 18 767 24
223 1...

result:

ok answer is correct. 1171 frames found

Test #16:

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

input:

1000 1000
.....................................................................................................................................................................................................................................................................................................

output:

1548
25 1 221 230
140 7 195 19
142 8 153 10
157 8 175 14
179 8 182 13
158 10 160 12
161 10 170 12
171 10 173 12
143 11 149 17
186 12 193 14
145 14 147 16
179 15 194 17
79 16 92 56
151 16 159 18
45 17 69 33
51 18 54 24
59 18 61 21
86 20 90 23
46 22 48 29
65 23 67 25
82 24 90 40
108 25 157 131
55 26 6...

result:

ok answer is correct. 1548 frames found

Test #17:

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

input:

1100 1100
.....................................................................................................................................................................................................................................................................................................

output:

1576
446 37 719 124
452 40 465 50
516 40 639 42
456 41 461 43
103 44 172 171
454 44 456 47
458 44 463 46
491 44 553 60
498 45 539 54
558 45 618 59
639 45 681 57
331 46 365 105
500 46 503 48
510 46 513 49
563 46 565 50
649 46 672 48
459 47 461 49
467 47 490 51
527 47 534 49
123 48 144 60
521 48 524 5...

result:

ok answer is correct. 1576 frames found

Test #18:

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

input:

1200 1200
.....................................................................................................................................................................................................................................................................................................

output:

2001
565 33 759 949
690 42 725 115
712 44 718 47
698 45 703 107
721 47 724 53
715 49 718 107
705 52 708 56
699 57 701 63
720 58 723 88
699 64 701 71
317 65 426 111
359 68 398 79
705 68 708 70
363 69 387 76
338 70 342 85
367 70 372 73
377 70 379 74
380 70 385 74
404 70 410 72
390 71 397 77
318 72 322...

result:

ok answer is correct. 2001 frames found

Test #19:

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

input:

1300 1300
.....................................................................................................................................................................................................................................................................................................

output:

1997
35 41 1062 62
48 42 455 44
459 42 499 46
537 42 612 44
797 42 826 44
886 42 920 47
890 43 894 45
1031 43 1051 49
895 44 898 46
900 44 912 46
914 44 918 46
1035 44 1039 47
143 45 164 51
241 45 246 57
1032 45 1034 47
1040 45 1047 47
261 46 287 50
146 47 151 50
155 47 162 49
242 47 244 50
317 48 7...

result:

ok answer is correct. 1997 frames found

Test #20:

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

input:

1400 1400
.....................................................................................................................................................................................................................................................................................................

output:

3028
819 14 1243 146
836 16 946 24
852 17 870 20
880 17 882 21
871 18 875 23
889 19 919 23
930 19 937 21
854 25 1048 42
975 26 1004 28
860 28 974 39
1020 28 1026 31
875 29 961 33
1029 29 1045 31
976 32 980 36
1000 32 1045 41
1188 32 1208 48
1002 33 1007 39
1201 33 1203 38
1009 34 1012 38
1017 34 103...

result:

ok answer is correct. 3028 frames found

Test #21:

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

input:

1500 1500
.....................................................................................................................................................................................................................................................................................................

output:

2367
232 24 1037 39
367 25 552 27
911 25 998 28
813 26 825 32
849 26 871 37
815 27 820 29
862 27 866 35
233 28 247 30
609 28 684 32
729 28 812 31
822 28 824 30
858 28 861 30
852 29 857 36
867 29 869 31
408 30 461 36
936 30 979 38
415 31 420 34
854 31 856 33
955 31 960 33
962 31 968 33
972 31 974 36
...

result:

ok answer is correct. 2367 frames found

Test #22:

score: 0
Accepted
time: 11ms
memory: 34840kb

input:

1600 1600
.....................................................................................................................................................................................................................................................................................................

output:

2887
401 67 620 219
569 68 603 82
586 69 593 75
421 70 431 135
443 70 474 72
581 70 584 75
587 71 589 73
590 71 592 73
424 72 428 89
575 72 579 78
432 73 520 78
487 74 492 76
437 75 439 77
440 75 456 77
468 75 476 77
497 75 502 77
503 75 517 77
583 77 597 80
598 77 601 81
432 85 549 99
415 86 420 19...

result:

ok answer is correct. 2887 frames found

Test #23:

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

input:

1700 1700
.....................................................................................................................................................................................................................................................................................................

output:

2913
936 2 1014 10
990 3 996 7
998 3 1010 8
937 4 942 7
946 4 950 9
1001 4 1003 6
951 5 968 7
979 5 987 8
1004 5 1008 7
972 7 976 9
110 53 959 144
406 54 915 63
419 55 439 60
465 55 467 59
614 55 759 58
804 55 852 61
868 55 870 60
224 56 293 58
476 56 546 58
831 56 849 58
423 57 436 59
586 57 595 59...

result:

ok answer is correct. 2913 frames found

Test #24:

score: 0
Accepted
time: 21ms
memory: 38940kb

input:

1800 1800
.....................................................................................................................................................................................................................................................................................................

output:

2988
333 1 466 83
338 5 355 31
358 5 398 13
360 6 365 9
366 6 368 11
374 6 391 10
341 7 344 16
370 7 373 11
394 7 397 11
408 7 450 12
431 8 447 10
416 9 420 11
421 9 425 11
345 10 348 16
362 10 365 12
349 14 352 30
363 16 378 20
390 17 425 20
444 20 452 54
693 20 1008 88
342 21 345 23
697 21 713 43
...

result:

ok answer is correct. 2988 frames found

Test #25:

score: 0
Accepted
time: 11ms
memory: 39192kb

input:

1900 1900
.....................................................................................................................................................................................................................................................................................................

output:

4115
494 5 864 224
801 10 826 55
815 11 824 21
527 12 545 49
817 12 819 15
820 12 822 15
531 13 538 15
804 13 814 18
542 15 544 20
808 15 812 17
529 16 532 32
816 16 818 19
819 16 822 18
534 19 537 34
757 19 760 221
805 19 809 27
539 20 541 28
602 20 753 35
649 21 676 23
689 21 710 25
625 22 635 26
...

result:

ok answer is correct. 4115 frames found

Test #26:

score: 0
Accepted
time: 22ms
memory: 39296kb

input:

2000 2000
.....................................................................................................................................................................................................................................................................................................

output:

3534
143 40 731 623
356 41 586 92
391 43 503 45
378 46 403 72
485 47 539 53
488 48 502 51
514 48 516 50
518 48 530 50
389 50 391 65
392 50 399 62
510 50 513 52
393 52 397 54
369 53 374 66
417 53 428 59
371 55 373 61
379 55 381 60
393 55 395 58
422 55 424 57
446 55 479 58
386 56 388 64
419 56 421 58
...

result:

ok answer is correct. 3534 frames found

Test #27:

score: 0
Accepted
time: 45ms
memory: 49956kb

input:

2000 1000
XXXXXXXXXXXXXXXXXX...XXXXXXXXXXXX...XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...XXXXXXXXXXXXXXXXXXXXXXXXXXX...XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...XXXXXX...XXXXXXXXXXXX...XXXXXXXXXXXXXXX...XXXXXXXXXXXXXXXXXX...XXXXX...

output:

192696
1 1 3 3
7 1 9 3
10 1 12 3
13 1 15 3
16 1 18 3
19 1 21 3
22 1 24 3
25 1 27 3
28 1 30 3
34 1 36 3
37 1 39 3
40 1 42 3
43 1 45 3
46 1 48 3
49 1 51 3
52 1 54 3
58 1 60 3
61 1 63 3
64 1 66 3
67 1 69 3
70 1 72 3
73 1 75 3
76 1 78 3
79 1 81 3
82 1 84 3
85 1 87 3
91 1 93 3
97 1 99 3
100 1 102 3
103 1...

result:

ok answer is correct. 192696 frames found

Test #28:

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

input:

2000 1000
....XXXX........XXX......XXXXXXX....XXX.............XXX.XXX..XXXXXXX.XXXXXXXXXX.....XXXX.XXXXXXX.............XXX....XXXX............XXX..........XXXXXXXXXX..XXX.XXX.XXXXXXXXXX..XXX.XXXXXX.XXX.XXXX....XXXX....XXXX....XXXX........XXX.........XXX......XXX.....XXXXXX.....XXXX.XXX.XXXXXX.XXX......

output:

124028
5 1 8 3
10 1 12 3
14 1 16 3
17 1 19 4
22 1 24 3
25 1 27 3
33 1 36 3
53 1 56 3
57 1 60 4
70 1 72 3
73 1 76 4
81 1 83 3
90 1 92 3
93 1 96 4
101 1 103 4
105 1 107 4
113 1 115 4
118 1 120 3
121 1 123 3
125 1 128 3
129 1 131 3
133 1 136 3
138 1 140 4
141 1 143 3
145 1 147 3
149 1 152 4
153 1 155 4...

result:

ok answer is correct. 124028 frames found

Test #29:

score: 0
Accepted
time: 29ms
memory: 45036kb

input:

2000 1000
..XXXXXX....XXX.......XXX.XXXX.XXX.....................XXX.........XXX.....XXXXX......XXX..XXX.XXX.......XXXXX......XXX...........XXXX.XXXX.XXX.......XXX........XXX......XXXXX.....XXXXXXXX..XXXXX.XXXXXXXXX......XXX..................XXX......XXX.XXXX..........................XXXXX..XXX........

output:

79956
6 1 8 4
28 1 30 4
41 1 45 3
46 1 48 3
63 1 65 5
67 1 69 5
77 1 80 3
81 1 85 3
86 1 88 4
91 1 93 4
103 1 105 5
108 1 110 3
116 1 118 5
122 1 124 4
126 1 130 4
133 1 135 3
138 1 140 5
142 1 144 5
151 1 155 3
156 1 160 5
162 1 164 5
168 1 170 4
187 1 189 4
193 1 195 3
212 1 214 5
227 1 229 5
242 ...

result:

ok answer is correct. 79956 frames found

Test #30:

score: 0
Accepted
time: 33ms
memory: 41724kb

input:

2000 1000
.XXXXX.XXXXX..XXXX...................XXX....................XXX.....................XXXX........XXX.....XXX..XXX....XXXX........XXXX.......XXXX...XXXX..XXX..XXXX........XXXX..............XXXX.XXXXX.XXXXXXXXXXXXXXXX...XXX............................XXXX.......XXXXX.............XXXXX.......X...

output:

55276
16 1 18 4
26 1 29 5
40 1 42 3
44 1 47 4
55 1 57 3
62 1 65 6
85 1 88 3
91 1 93 4
133 1 135 3
176 1 179 5
182 1 186 4
189 1 192 4
202 1 204 3
223 1 227 6
272 1 274 5
289 1 291 4
301 1 305 5
307 1 310 5
355 1 359 6
363 1 365 5
374 1 378 6
380 1 382 5
397 1 400 5
429 1 432 5
436 1 438 3
441 1 444 ...

result:

ok answer is correct. 55276 frames found

Test #31:

score: 0
Accepted
time: 23ms
memory: 40120kb

input:

2000 1000
........................XXXXXX...XXXX.............XXXXXX............................................................XXX.XXX...........XXXX...............................................XXXXX.....................XXXXXX....XXXXXXXX................................................................

output:

23553
32 1 35 5
41 1 50 6
84 1 88 3
106 1 109 5
122 1 130 4
194 1 198 8
206 1 210 8
213 1 216 9
264 1 266 6
271 1 280 3
321 1 327 4
336 1 339 7
344 1 350 7
353 1 359 6
406 1 410 9
413 1 417 7
427 1 430 9
443 1 449 9
453 1 459 3
501 1 508 6
518 1 520 5
525 1 528 7
555 1 557 3
584 1 588 7
601 1 604 9
...

result:

ok answer is correct. 23553 frames found

Test #32:

score: 0
Accepted
time: 17ms
memory: 39404kb

input:

2000 1000
..........................................................................................................................................................................................................XXXXXXXXXXXXXXXX................................XXXXXXXXXXXXXXXX...........................

output:

7934
93 1 96 4
152 1 156 11
982 1 999 22
1508 1 1510 13
1931 1 1940 4
646 2 648 24
756 2 759 11
784 2 798 19
805 2 811 14
1061 2 1064 12
1331 2 1338 19
1416 2 1421 23
1479 2 1482 6
402 3 414 5
584 3 587 13
791 3 796 6
1177 3 1179 17
1227 3 1235 5
1333 3 1336 10
1531 3 1550 11
1958 3 1966 25
104 4 11...

result:

ok answer is correct. 7934 frames found

Test #33:

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

input:

2000 1000
.....................................................................................................................................................................................................................................................................................................

output:

3925
1555 1 1589 18
76 2 92 5
527 2 530 13
612 2 619 4
751 2 793 19
1041 2 1045 32
325 3 339 47
753 3 762 10
770 3 780 8
782 3 786 16
1558 3 1565 7
1569 3 1586 8
459 4 478 40
1573 4 1575 6
1576 4 1580 6
772 5 778 7
1207 5 1221 46
1581 5 1583 7
467 6 471 21
755 6 759 9
1101 6 1138 43
1310 6 1343 47
4...

result:

ok answer is correct. 3925 frames found

Test #34:

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

input:

2000 1000
.....................................................................................................................................................................................................................................................................................................

output:

2022
329 1 376 95
1620 2 1637 12
1141 3 1174 34
1622 3 1627 10
340 4 360 6
366 4 374 31
1633 4 1635 10
1319 5 1341 7
1624 6 1626 8
1629 6 1631 10
368 7 372 10
1160 7 1166 12
644 8 663 100
1162 8 1164 10
334 9 351 19
347 10 349 12
1145 10 1159 12
1718 10 1793 13
339 11 346 13
371 11 373 13
645 13 655...

result:

ok answer is correct. 2022 frames found

Test #35:

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

input:

2000 1000
.....................................................................................................................................................................................................................................................................................................

output:

1101
120 6 158 178
1230 11 1279 143
848 15 885 71
853 16 876 19
133 17 135 133
849 17 851 28
1240 19 1245 115
854 20 880 43
855 22 872 27
866 23 869 25
859 24 861 26
875 25 879 31
1248 25 1253 70
1057 27 1187 186
139 28 143 127
856 28 863 35
1883 29 1954 79
858 30 860 33
1086 31 1105 64
1250 32 1252...

result:

ok answer is correct. 1101 frames found

Test #36:

score: 0
Accepted
time: 11ms
memory: 39208kb

input:

2000 1000
.....................................................................................................................................................................................................................................................................................................

output:

329
841 7 910 475
871 98 885 101
135 108 293 145
261 109 288 112
143 110 189 114
136 115 158 120
140 116 142 118
143 116 145 118
186 116 251 119
147 117 155 119
220 120 237 123
252 123 257 126
261 123 282 137
137 124 163 141
272 125 276 129
140 126 147 128
159 127 161 133
263 127 267 129
170 128 250...

result:

ok answer is correct. 329 frames found

Test #37:

score: 0
Accepted
time: 30ms
memory: 39116kb

input:

2000 2000
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

502
1 1 2000 2000
2 3 1998 1998
3 5 1996 1996
4 7 1994 1994
5 9 1992 1992
6 11 1990 1990
7 13 1988 1988
8 15 1986 1986
9 17 1984 1984
10 19 1982 1982
11 21 1980 1980
12 23 1978 1978
13 25 1976 1976
14 27 1974 1974
15 29 1972 1972
16 31 1970 1970
17 33 1968 1968
18 35 1966 1966
19 37 1964 1964
20 39 ...

result:

ok answer is correct. 502 frames found

Test #38:

score: 0
Accepted
time: 26ms
memory: 39172kb

input:

2000 2000
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

503
1 1 2000 2000
3 3 1999 1998
5 5 1998 1996
7 7 1996 1995
9 9 1995 1993
11 11 1994 1991
13 13 1993 1989
15 15 1992 1987
17 17 1991 1985
19 18 1989 1983
21 20 1988 1981
23 22 1987 1979
25 24 1986 1977
27 26 1985 1975
29 28 1984 1973
31 30 1983 1971
33 32 1982 1969
35 34 1980 1968
37 36 1979 1966
39...

result:

ok answer is correct. 503 frames found

Test #39:

score: 0
Accepted
time: 21ms
memory: 39136kb

input:

2000 2000
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

503
1 1 2000 2000
3 3 1998 1999
5 5 1996 1998
7 7 1994 1997
9 9 1992 1996
11 11 1990 1995
13 13 1988 1994
15 15 1986 1993
17 17 1985 1991
19 19 1983 1990
21 21 1981 1989
23 23 1979 1988
25 25 1977 1987
27 27 1975 1986
29 29 1973 1985
31 31 1971 1984
33 33 1969 1983
35 35 1967 1982
37 37 1965 1981
39...

result:

ok answer is correct. 503 frames found

Test #40:

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

input:

2000 2000
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

502
1 1 2000 2000
3 2 1998 1998
5 3 1996 1996
7 4 1994 1994
9 5 1992 1992
11 6 1990 1990
13 7 1988 1988
15 8 1986 1986
17 9 1984 1984
19 10 1982 1982
21 11 1980 1980
23 12 1978 1978
25 13 1976 1976
27 14 1974 1974
29 15 1972 1972
31 16 1970 1970
33 17 1968 1968
35 18 1966 1966
37 19 1964 1964
39 20 ...

result:

ok answer is correct. 502 frames found

Test #41:

score: 0
Accepted
time: 22ms
memory: 39204kb

input:

2000 2000
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

567
1 1 2000 2000
3 2 1998 1998
5 4 1996 1997
6 6 1994 1995
8 7 1992 1993
10 9 1991 1991
12 11 1989 1990
14 13 1988 1988
16 15 1986 1987
18 16 1984 1985
20 18 1983 1983
21 20 1981 1981
23 22 1979 1980
25 24 1977 1979
26 26 1975 1977
28 27 1973 1975
30 29 1971 1974
31 31 1969 1972
33 33 1968 1970
35 ...

result:

ok answer is correct. 567 frames found

Test #42:

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

input:

1000 1000
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

82461
1 1 1000 1000
5 2 7 4
8 2 10 4
11 2 13 4
14 2 16 4
17 2 19 4
20 2 22 4
23 2 25 4
26 2 28 4
29 2 31 4
32 2 34 4
35 2 37 4
38 2 40 4
41 2 43 4
44 2 46 4
47 2 49 4
50 2 52 4
53 2 55 4
56 2 58 4
59 2 61 4
62 2 64 4
65 2 67 4
68 2 70 4
71 2 73 4
74 2 76 4
77 2 79 4
80 2 82 4
83 2 85 4
86 2 88 4
89 ...

result:

ok answer is correct. 82461 frames found

Test #43:

score: 0
Accepted
time: 21ms
memory: 29096kb

input:

1000 1000
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

49304
1 1 1000 1000
6 2 9 5
10 2 13 5
14 2 17 5
18 2 21 5
22 2 25 5
26 2 29 5
30 2 33 5
34 2 37 5
38 2 41 5
42 2 45 5
46 2 49 5
50 2 53 5
54 2 57 5
58 2 61 5
62 2 65 5
66 2 69 5
70 2 73 5
74 2 77 5
78 2 81 5
82 2 85 5
86 2 89 5
90 2 93 5
94 2 97 5
98 2 101 5
102 2 105 5
106 2 109 5
110 2 113 5
114 2...

result:

ok answer is correct. 49304 frames found

Test #44:

score: 0
Accepted
time: 25ms
memory: 33348kb

input:

1001 1001
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

110886
1 1 1001 1001
5 2 7 4
8 2 10 4
11 2 13 4
14 2 16 4
17 2 19 4
20 2 22 4
23 2 25 4
26 2 28 4
29 2 31 4
32 2 34 4
35 2 37 4
38 2 40 4
41 2 43 4
44 2 46 4
47 2 49 4
50 2 52 4
53 2 55 4
56 2 58 4
59 2 61 4
62 2 64 4
65 2 67 4
68 2 70 4
71 2 73 4
74 2 76 4
77 2 79 4
80 2 82 4
83 2 85 4
86 2 88 4
89...

result:

ok answer is correct. 110886 frames found

Test #45:

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

input:

1002 1002
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

62497
1 1 1002 1002
6 2 9 5
10 2 13 5
14 2 17 5
18 2 21 5
22 2 25 5
26 2 29 5
30 2 33 5
34 2 37 5
38 2 41 5
42 2 45 5
46 2 49 5
50 2 53 5
54 2 57 5
58 2 61 5
62 2 65 5
66 2 69 5
70 2 73 5
74 2 77 5
78 2 81 5
82 2 85 5
86 2 89 5
90 2 93 5
94 2 97 5
98 2 101 5
102 2 105 5
106 2 109 5
110 2 113 5
114 2...

result:

ok answer is correct. 62497 frames found

Test #46:

score: 0
Accepted
time: 19ms
memory: 29428kb

input:

1000 1000
XXXXX........................XXXXX........................XXXXX........................XXXXX........................XXXXX........................XXXXX........................XXXXX........................XXXXX........................XXXXX........................XXXXX...........................

output:

34208
1 1 5 5
30 1 34 5
59 1 63 5
88 1 92 5
117 1 121 5
146 1 150 5
175 1 179 5
204 1 208 5
233 1 237 5
262 1 266 5
291 1 295 5
320 1 324 5
349 1 353 5
378 1 382 5
407 1 411 5
436 1 440 5
465 1 469 5
494 1 498 5
523 1 527 5
552 1 556 5
581 1 585 5
610 1 614 5
639 1 643 5
668 1 672 5
697 1 701 5
726 ...

result:

ok answer is correct. 34208 frames found

Test #47:

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

input:

1000 1000
XXXXXX.........XXXXXX.........XXXXXX.........XXXXXX.........XXXXXX.........XXXXXX.........XXXXXX.........XXXXXX.........XXXXXX.........XXXXXX.........XXXXXX.........XXXXXX.........XXXXXX.........XXXXXX.........XXXXXX.........XXXXXX.........XXXXXX.........XXXXXX.........XXXXXX.........XXXXX...

output:

22045
1 1 6 6
16 1 21 6
31 1 36 6
46 1 51 6
61 1 66 6
76 1 81 6
91 1 96 6
106 1 111 6
121 1 126 6
136 1 141 6
151 1 156 6
166 1 171 6
181 1 186 6
196 1 201 6
211 1 216 6
226 1 231 6
241 1 246 6
256 1 261 6
271 1 276 6
286 1 291 6
301 1 306 6
316 1 321 6
331 1 336 6
346 1 351 6
361 1 366 6
376 1 381 ...

result:

ok answer is correct. 22045 frames found

Test #48:

score: 0
Accepted
time: 24ms
memory: 32972kb

input:

1000 1000
XXX.......XXX.......XXX.......XXX.......XXX.......XXX.......XXX.......XXX.......XXX.......XXX.......XXX.......XXX.......XXX.......XXX.......XXX.......XXX.......XXX.......XXX.......XXX.......XXX.......XXX.......XXX.......XXX.......XXX.......XXX.......XXX.......XXX.......XXX.......XXX..........

output:

99600
1 1 3 3
11 1 13 3
21 1 23 3
31 1 33 3
41 1 43 3
51 1 53 3
61 1 63 3
71 1 73 3
81 1 83 3
91 1 93 3
101 1 103 3
111 1 113 3
121 1 123 3
131 1 133 3
141 1 143 3
151 1 153 3
161 1 163 3
171 1 173 3
181 1 183 3
191 1 193 3
201 1 203 3
211 1 213 3
221 1 223 3
231 1 233 3
241 1 243 3
251 1 253 3
261 ...

result:

ok answer is correct. 99600 frames found