QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#227198#7190. ChessboardPPP#TL 2403ms5540kbC++174.6kb2023-10-27 01:28:262023-10-27 01:28:27

Judging History

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

  • [2023-10-27 01:28:27]
  • 评测
  • 测评结果:TL
  • 用时:2403ms
  • 内存:5540kb
  • [2023-10-27 01:28:26]
  • 提交

answer

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
#pragma GCC optimize("O3")

#include<bits/stdc++.h>

using namespace std;

#define pb push_back

typedef long long ll;
typedef double ld;
int n, m;
const int maxN = 205;
int cnt_other[4 * maxN];
int info[4 * maxN][maxN][2];
int tp[maxN][maxN];
int q;
int par[4 * maxN];
int rnk[4 * maxN];

int get(int x) {
    if (x == par[x]) return x;
    return par[x] = get(par[x]);
}

void unite(int a, int b) {
    a = get(a);
    b = get(b);
    if (a == b) return;
    if (rnk[b] < rnk[a]) swap(a, b);
    if (rnk[b] == rnk[a]) rnk[b]++;
    par[a] = b;
}

bool was[4 * maxN];
int MP[4 * maxN];
int SZ[4 * maxN];
int EDGE[2 * maxN][2 * maxN];
int CNT[4 * maxN];
int id[4 * maxN];
int Q[4 * maxN];
int ITER = 0;
int inter[4 * maxN];

void merge(int v, int l, int mid, int r) {
    cnt_other[v] = cnt_other[2 * v] + cnt_other[2 * v + 1];
    int SZ1 = SZ[2 * v];
    int SZ2 = SZ[2 * v + 1];
    for (int u = 0; u < SZ1; u++) {
        CNT[2 * u] = 0;
        id[2 * u] = -1;
    }
    for (int u = 0; u < SZ2; u++) {
        CNT[2 * u + 1] = 0;
        id[2 * u + 1] = -1;
    }
    for (int x = 1; x <= m; x++) {
        if (tp[mid][x] == tp[mid + 1][x]) {
            int P = info[2 * v][x][1] * 2;
            int Q = info[2 * v + 1][x][0] * 2 + 1;
            EDGE[P][CNT[P]] = Q;
            EDGE[Q][CNT[Q]] = P;
            CNT[P]++;
            CNT[Q]++;
        }
    }
    int CMP = 0;
    for (int u = 0; u < SZ1; u++) {
        if (id[2 * u] == -1) {
            ++CMP;
            int topQ = 0;
            Q[topQ++] = 2 * u;
            id[2 * u] = 2 * u;
            for (int z = 0; z < topQ; z++) {
                int vert = Q[z];
                for (int p = 0; p < CNT[vert]; p++) {
                    if (id[EDGE[vert][p]] == -1) {
                        id[EDGE[vert][p]] = 2 * u;
                        Q[topQ++] = EDGE[vert][p];
                    }
                }
            }
        }
    }
    for (int u = 0; u < SZ2; u++) {
        if (id[2 * u + 1] == -1) {
            ++CMP;
            id[2 * u + 1] = 2 * u + 1;
        }
    }
    ITER++;
    for (int x = 1; x <= m; x++) {
        inter[id[info[2 * v][x][0] * 2]] = ITER;
        inter[id[info[2 * v + 1][x][1] * 2 + 1]] = ITER;
    }
    int sz = 0;
    for (int j = 0; j < 2 * SZ1; j += 2) {
        if (inter[j] == ITER) {
            CMP--;
            MP[j] = sz;
            sz++;
        }
    }
    for (int j = 1; j < 2 * SZ2; j += 2) {
        if (inter[j] == ITER) {
            CMP--;
            MP[j] = sz;
            sz++;
        }
    }

    cnt_other[v] += CMP;
    for (int x = 1; x <= m; x++) {
        info[v][x][0] = MP[id[info[2 * v][x][0] * 2]];
        info[v][x][1] = MP[id[info[2 * v + 1][x][1] * 2 + 1]];
    }
    SZ[v] = sz;
}

void build(int v, int tl, int tr) {
    if (tl == tr) {
        cnt_other[v] = 0;
        int sz = 0;
        for (int j = 1; j <= m; j++) {
            if (j == 1 || tp[tl][j] != tp[tl][j - 1]) {
                info[v][j][0] = info[v][j][1] = sz;
                sz++;
            } else {
                info[v][j][0] = info[v][j][1] = info[v][j - 1][0];
            }
        }
        SZ[v] = sz;
        return;
    }
    int tm = (tl + tr) / 2;
    build(2 * v, tl, tm);
    build(2 * v + 1, tm + 1, tr);
    merge(v, tl, tm, tr);
}

int calc() {
    return SZ[1] + cnt_other[1];
}

void upd(int v, int tl, int tr, int pos) {
    if (tl == tr) {
        cnt_other[v] = 0;
        int sz = 0;
        for (int j = 1; j <= m; j++) {
            if (j == 1 || tp[tl][j] != tp[tl][j - 1]) {
                info[v][j][0] = info[v][j][1] = sz;
                sz++;
            } else {
                info[v][j][0] = info[v][j][1] = info[v][j - 1][0];
            }
        }
        SZ[v] = sz;
        return;
    }
    int tm = (tl + tr) / 2;
    if (pos <= tm) {
        upd(2 * v, tl, tm, pos);
    } else {
        upd(2 * v + 1, tm + 1, tr, pos);
    }
    merge(v, tl, tm, tr);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            char c;
            cin >> c;
            if (c == '1') tp[i][j] = 1;
        }
    }
    build(1, 1, n);
    int op = calc();
    while (q--) {
        int x, y;
        cin >> x >> y;
        x ^= op;
        y ^= op;
        tp[x][y] ^= 1;
        upd(1, 1, n, x);
        op = calc();
        cout << op << '\n';
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 2 2
01
10
5 5
0 0

output:

2
1

result:

ok 2 number(s): "2 1"

Test #2:

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

input:

1 1 1
0
0 0

output:

1

result:

ok 1 number(s): "1"

Test #3:

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

input:

5 5 5
10111
11110
10010
00111
00101
4 1
5 4
12 11
12 13
13 9

output:

7
9
9
8
8

result:

ok 5 number(s): "7 9 9 8 8"

Test #4:

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

input:

5 5 5
00010
10000
11110
00001
01011
5 2
7 1
3 5
1 1
4 4

output:

5
6
5
6
6

result:

ok 5 number(s): "5 6 5 6 6"

Test #5:

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

input:

5 5 5
10010
10100
11100
11100
01000
0 4
1 7
1 1
4 0
7 6

output:

4
4
5
5
4

result:

ok 5 number(s): "4 4 5 5 4"

Test #6:

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

input:

5 5 5
00101
01011
00010
11000
01010
9 12
7 7
13 9
3 4
11 11

output:

6
8
7
9
7

result:

ok 5 number(s): "6 8 7 9 7"

Test #7:

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

input:

5 5 5
10101
00111
00100
10100
01000
10 12
9 11
6 4
10 12
10 12

output:

8
7
8
8
8

result:

ok 5 number(s): "8 7 8 8 8"

Test #8:

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

input:

5 5 5
01100
00001
11010
10010
01100
9 10
9 12
11 11
9 9
11 8

output:

8
9
10
10
9

result:

ok 5 number(s): "8 9 10 10 9"

Test #9:

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

input:

5 5 5
11011
11001
11111
11110
01111
0 1
2 1
2 2
2 2
2 2

output:

3
3
3
3
3

result:

ok 5 number(s): "3 3 3 3 3"

Test #10:

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

input:

5 5 5
01011
10101
00001
00011
01101
13 10
10 13
13 12
15 9
9 9

output:

8
9
12
10
10

result:

ok 5 number(s): "8 9 12 10 10"

Test #11:

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

input:

5 5 5
11010
10011
00011
00111
00111
0 1
1 0
6 1
0 1
1 7

output:

5
4
4
5
5

result:

ok 5 number(s): "5 4 4 5 5"

Test #12:

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

input:

5 5 5
11100
10011
01001
01010
01110
6 3
2 7
4 6
0 1
7 3

output:

6
7
5
6
5

result:

ok 5 number(s): "6 7 5 6 5"

Test #13:

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

input:

10 10 10
0010011100
1010001100
0100110111
1000011111
1000000110
1110000011
0010111100
0100011001
1110100001
0001101100
17 17
20 19
25 20
18 18
23 17
24 16
20 23
22 20
26 22
26 20

output:

17
17
16
18
18
19
19
19
19
19

result:

ok 10 numbers

Test #14:

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

input:

10 10 10
1110001110
0101101010
1111101001
1011101110
0000111100
1001100100
1000101000
0000111011
1111001010
1101000011
10 14
10 9
12 6
5 4
6 15
7 12
10 15
10 6
11 5
13 11

output:

14
15
13
14
13
14
15
15
15
14

result:

ok 10 numbers

Test #15:

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

input:

10 10 10
1100011101
0110001100
1111110101
0001010001
0110010110
1101100100
1101010000
1101110001
0010110110
1110101111
22 19
19 22
29 17
17 28
19 17
19 20
31 23
19 20
18 29
28 22

output:

21
20
21
21
23
22
21
21
21
19

result:

ok 10 numbers

Test #16:

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

input:

10 10 10
0000001110
1001110001
0100111111
0010110100
0110101110
1110011011
1011000110
1000011001
0011001101
0010001000
24 23
17 28
21 30
28 29
29 24
24 20
17 29
18 25
17 28
24 19

output:

20
22
24
25
28
24
24
25
25
23

result:

ok 10 numbers

Test #17:

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

input:

10 10 10
1000110010
1100010111
0100100011
1010000010
1110010101
1010011110
0011110011
1100011011
1011000101
1110100100
17 28
21 30
28 18
19 30
16 17
19 29
19 20
30 17
31 17
21 16

output:

22
22
20
20
21
23
22
21
23
23

result:

ok 10 numbers

Test #18:

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

input:

10 10 10
0010110001
1111100001
0011111101
1001011011
1110111101
1101111101
0101101101
0001110001
0010111100
1011000011
22 23
19 20
22 26
21 22
19 21
26 18
12 13
21 23
21 25
21 22

output:

17
18
16
17
16
15
16
16
16
16

result:

ok 10 numbers

Test #19:

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

input:

10 10 10
1110100010
0001000100
1001001000
1011111100
0110001111
1011110000
1001011001
0101111111
0011000010
0111101011
22 19
18 28
31 18
29 17
28 19
31 22
31 17
20 17
31 18
18 20

output:

21
21
20
20
21
23
23
23
22
21

result:

ok 10 numbers

Test #20:

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

input:

10 10 10
1110110000
0010101110
1000010010
0100000001
0000110101
1110010001
1001100111
0000010101
1000101011
0010011100
17 17
19 30
16 22
17 31
16 23
19 18
17 28
24 27
19 24
24 26

output:

22
21
22
22
23
24
25
26
27
25

result:

ok 10 numbers

Test #21:

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

input:

10 10 10
0000000011
1111011001
0010001110
0111110111
0000011101
1000010110
1111110111
1000010111
1000010011
1110110000
12 0
13 11
8 15
0 15
12 2
14 0
8 15
12 9
10 10
15 3

output:

9
9
10
10
10
11
11
11
11
12

result:

ok 10 numbers

Test #22:

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

input:

10 10 10
1010000001
0111001100
1011001001
1011110010
0110011011
0110000111
0110000011
1111110001
0100001110
0000001110
18 18
22 18
21 22
26 24
24 16
21 19
23 22
17 21
17 21
25 17

output:

17
17
16
17
17
16
16
18
19
20

result:

ok 10 numbers

Test #23:

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

input:

50 50 50
11110010100001100100010000100100010111001101010111
00100110100101010011100111011101000110001111111111
00000100111011001011110101001011101111100100101011
00010001110010011110001100001100100001110111111001
01001010010100010000101100111000011010101000001101
110000110101110010011011110101100101...

output:

370
371
373
373
371
373
374
376
374
373
372
372
374
374
372
373
373
373
372
372
373
373
374
373
373
372
372
374
375
376
374
373
374
374
374
373
373
373
373
376
376
376
377
377
378
379
380
379
378
378

result:

ok 50 numbers

Test #24:

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

input:

50 50 50
10110110011010000110111101011100011110111001101111
01000111110100100111110001010001011000110000011111
01000111101101000100100110011101001100111011110100
00110110111110001111010011111101110100111101110011
00011001010000011001000100110010110111010011110111
110101110111001000100100110000111101...

output:

346
346
349
349
350
351
350
350
348
349
348
347
348
348
349
348
348
349
349
349
349
348
346
346
347
346
344
343
342
344
345
345
344
342
344
343
343
345
345
345
345
345
346
345
345
345
345
344
344
342

result:

ok 50 numbers

Test #25:

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

input:

50 50 50
00011010101101101011111100101110101001110011010101
00111111101010011101000001111011010010110100110000
10110011011110001111100101001101110110010101001010
10011011011011001011101000010000111011011111101111
01110000111110011110110100110100100011011100000000
010110001001010001110111110110110001...

output:

396
395
396
395
397
396
397
396
396
396
395
395
395
395
395
397
399
399
399
398
398
400
399
400
400
401
401
402
400
403
403
403
403
402
402
403
405
407
407
405
405
405
405
406
405
404
404
404
404
405

result:

ok 50 numbers

Test #26:

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

input:

50 50 50
10011110100010011101000111010110010100000011111101
00111100011110001001000111011011001101101000010110
01010010011110101000111100001110110000000000110111
01111100011011010010100111110001111111101110100000
00100011111111110011000100101110110010000101010010
101101010111101011001000011010101101...

output:

362
365
366
365
367
369
367
366
366
366
362
363
363
364
365
365
365
366
366
365
366
366
366
366
368
370
369
368
368
370
371
371
370
368
367
367
365
364
364
365
365
366
367
366
365
364
364
364
363
364

result:

ok 50 numbers

Test #27:

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

input:

50 50 50
01111000010011111011000011110110111101010011000111
01000100000100111111010111010001010011000101101011
10001010001000100111001111010000001011101110101001
01001011011101000000111000001100010100001100110110
01011010111001110100001101100100110101000111101100
001100100101000011011010001111100011...

output:

373
376
377
376
374
370
370
369
368
367
366
366
366
362
362
362
361
364
364
364
363
363
363
365
366
367
369
368
369
368
369
369
368
369
370
371
371
370
369
372
371
371
371
372
372
369
370
367
367
368

result:

ok 50 numbers

Test #28:

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

input:

50 50 50
11111100101101000110101010001000000011101011111100
00000001110000100011100001111011000001010001001101
01101100011010111000011100000010001101110001011110
11101111110000000001101011101101000011010110111110
00000001100001101001111101101010101000111000111111
101110111011110001101101001011110111...

output:

343
344
344
342
340
339
340
341
342
341
342
342
339
339
338
340
339
339
340
342
342
342
342
341
341
340
338
337
338
337
335
332
335
336
335
335
335
337
333
333
335
334
333
333
333
334
334
333
331
331

result:

ok 50 numbers

Test #29:

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

input:

50 50 50
10110101001110100000100111111001100110101101011000
01111010100110010101110100010011001111111101100000
00111101011101011000001010010101110111000101100001
01001000110000010001010110000000001110110100100001
00110000100111001010011001100000011100110011001001
010101010000101001010110101110111010...

output:

363
363
362
361
361
363
363
363
363
364
364
364
364
363
364
367
367
367
366
366
366
366
366
364
364
364
363
363
363
361
362
361
361
362
364
366
367
367
366
364
363
362
364
365
365
365
365
362
363
362

result:

ok 50 numbers

Test #30:

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

input:

50 50 50
00010001110001000111000110000011011101011101100010
00011010011111001000100110111001010000101100001110
11010001001111010111011001000111000100001010111111
01101111100111001100001001110001101100010110001101
01111011101111000111101001101100011101101100100011
110100000110010010000001101010100110...

output:

340
340
343
342
342
342
343
342
342
340
340
341
341
342
342
341
341
341
340
341
340
340
340
340
339
341
342
341
341
341
340
340
339
338
339
338
338
338
337
338
339
339
339
338
339
340
340
340
342
342

result:

ok 50 numbers

Test #31:

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

input:

50 50 50
10010101010010110011001001110011110000000101001000
00000011001001111010010010110001101010100000101011
00100000011011011000001010010101001010110100000000
11001010000011001110000010011110110001001101010111
00001000001000000010110000111111001010100101110100
000111011000101010111011110110111110...

output:

345
344
344
343
342
343
343
344
343
344
343
344
345
348
348
349
348
351
351
351
351
352
353
351
351
349
348
352
351
352
352
353
352
351
350
348
347
347
345
345
346
345
345
346
346
345
347
347
344
345

result:

ok 50 numbers

Test #32:

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

input:

50 50 50
00010100101000100000101011110101100101110011101100
00100111010000001110011100111011111101011010101101
11011110110010010000100111011001101011100000110000
10001011011100000000100111001000101110001011110000
00110000100110110010000001110001000111111100110110
100101101111101110011011111011010110...

output:

366
362
362
363
363
364
363
364
364
360
361
361
361
361
361
361
361
360
360
360
359
358
357
356
356
356
356
355
354
355
353
351
349
350
348
348
349
348
347
349
349
349
350
351
350
350
351
352
352
353

result:

ok 50 numbers

Test #33:

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

input:

100 100 100
0000010000111011110000111110110100111010110110001000001110000001100111100100110101101110101010001011
1111011001001111001101101101101011000110111100100011100011110010000001110101011000010011110110101001
11000110011101000111011000010010000001101000100100111110011101101101011001000100101010...

output:

1378
1378
1378
1377
1377
1377
1377
1377
1377
1376
1376
1377
1379
1379
1379
1380
1380
1381
1380
1380
1381
1379
1380
1382
1382
1383
1384
1384
1382
1383
1383
1382
1383
1383
1383
1382
1381
1382
1382
1382
1382
1382
1382
1383
1384
1384
1384
1384
1384
1383
1382
1382
1383
1384
1384
1383
1386
1387
1387
1387
...

result:

ok 100 numbers

Test #34:

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

input:

100 100 100
0011110001010101110011111101011101101011000010110110100011101111010011101001000000101010110100101100
1010100101111000101100001100100100110010111111110000011110010101001101110100000100101011001010011010
10000100111011100110001100001110011001010010010011000000110000101100100111000011000111...

output:

1375
1374
1377
1375
1376
1376
1376
1376
1376
1376
1375
1375
1375
1375
1377
1379
1380
1379
1380
1379
1380
1381
1382
1381
1380
1382
1382
1380
1379
1381
1381
1382
1381
1380
1380
1379
1378
1378
1376
1377
1378
1379
1379
1380
1383
1384
1383
1383
1382
1382
1382
1383
1383
1384
1383
1381
1381
1382
1382
1382
...

result:

ok 100 numbers

Test #35:

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

input:

100 100 100
0111000110110110010001000011000100001101010001010001001001111000010010100011000001001000100011101110
1011000111100111100010111001010000101011100011101101110000100101010010111000001000100110001000100011
11000011010101110000000001001011001110000000001100000100000001001011110010010001110100...

output:

1370
1366
1368
1367
1366
1367
1367
1368
1368
1368
1368
1367
1367
1367
1366
1366
1366
1364
1364
1365
1365
1366
1367
1369
1369
1368
1369
1369
1368
1371
1368
1369
1369
1369
1369
1370
1369
1369
1370
1371
1370
1370
1370
1369
1371
1372
1372
1373
1373
1372
1371
1371
1371
1372
1372
1374
1373
1373
1373
1373
...

result:

ok 100 numbers

Test #36:

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

input:

100 100 100
1010100111010000010011111100110011010110101100001111010100110010101110100010011001111111101100000001
1110101110101100000101001010111011100010110000101001000110000010001010110000000001110110100100001001
10000100111001010011001100000011100110011001001010101010000101001010110101110111010001...

output:

1394
1396
1392
1390
1390
1390
1389
1389
1390
1389
1391
1392
1391
1391
1391
1393
1392
1392
1392
1394
1393
1393
1392
1391
1391
1390
1389
1390
1390
1391
1390
1389
1388
1389
1388
1387
1386
1386
1384
1383
1383
1384
1381
1381
1381
1377
1377
1377
1377
1377
1377
1378
1378
1379
1378
1378
1378
1378
1378
1378
...

result:

ok 100 numbers

Test #37:

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

input:

100 100 100
1001110000010010010101000010111010010100101110100001110110010100101010001001001100010111010111100011
1111000000011010000100011011110100010110010101010100111010110000110110100100011101101110001100111000
01010110011010000110000000010100110111100011010101010011101110101101100111110100111010...

output:

1424
1424
1424
1424
1425
1426
1427
1426
1426
1426
1424
1425
1424
1424
1424
1425
1426
1427
1427
1425
1426
1425
1423
1424
1423
1423
1424
1423
1422
1421
1421
1420
1420
1420
1421
1419
1418
1418
1417
1416
1415
1415
1414
1414
1415
1413
1413
1415
1415
1413
1415
1415
1415
1415
1415
1414
1414
1416
1414
1413
...

result:

ok 100 numbers

Test #38:

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

input:

100 100 100
1101010001110100010110000011101010100010010001011111011010010010011011010101001110110101001000000001
1011111000000101001010101010000001001101001111001000010101010101111010101100010001110011010000000001
00011001110100010101011101010000111101110001010010111101001011100000111000100000101111...

output:

1383
1381
1381
1383
1383
1383
1385
1386
1386
1385
1386
1384
1385
1385
1383
1382
1384
1383
1382
1382
1383
1383
1383
1383
1381
1381
1381
1384
1385
1385
1384
1381
1381
1381
1381
1384
1384
1383
1383
1384
1383
1381
1381
1380
1383
1382
1383
1385
1384
1384
1384
1383
1383
1382
1379
1379
1379
1379
1381
1381
...

result:

ok 100 numbers

Test #39:

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

input:

100 100 100
0000111111011111011100111101010001100001000000011000100001011001011111011110010111110010000100110100
1010110001000010101101011111001010010101011000001101101001100110100100001001001010111011110000100011
01011110011000110001110000001100001100001011001101110001100110000001101111000010000101...

output:

1402
1402
1402
1401
1401
1401
1401
1403
1404
1403
1402
1402
1399
1398
1397
1397
1399
1398
1399
1398
1397
1398
1397
1397
1395
1394
1393
1393
1393
1392
1392
1393
1392
1391
1391
1392
1392
1391
1392
1392
1392
1393
1393
1393
1393
1392
1392
1392
1393
1393
1391
1392
1393
1393
1393
1392
1391
1391
1390
1390
...

result:

ok 100 numbers

Test #40:

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

input:

100 100 100
0011001110101001111100000010011000111011101110100110101111111111101011010110110010000000011011110110
0111011011011001100101101111101101010000011001010001001111000110111000000111000110100010111010011110
10011000110110101010111101001001000010010001001100001001000110000110111011000101110000...

output:

1361
1361
1361
1361
1361
1361
1361
1362
1362
1362
1363
1362
1361
1361
1362
1361
1361
1361
1362
1364
1363
1362
1362
1361
1362
1363
1366
1366
1366
1366
1366
1367
1366
1366
1366
1366
1366
1368
1367
1367
1367
1366
1366
1365
1365
1366
1366
1365
1363
1362
1363
1363
1362
1362
1362
1362
1364
1363
1365
1367
...

result:

ok 100 numbers

Test #41:

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

input:

100 100 100
0111101001001111111011011100101001001100111111101000001010110001101000111101100010100100000000011101
0110100110100111000010001110010000101001000110100100110011110001100000001111001010110110010111101110
11111011010000001101100001000101010011000010010010100111101001100110110000010111010011...

output:

1297
1298
1296
1296
1296
1295
1295
1294
1294
1295
1297
1297
1298
1299
1302
1299
1299
1299
1298
1296
1296
1297
1295
1295
1295
1295
1293
1294
1294
1296
1294
1292
1293
1293
1296
1298
1298
1297
1298
1298
1296
1297
1298
1296
1296
1295
1294
1296
1295
1295
1293
1292
1290
1290
1290
1290
1290
1291
1290
1289
...

result:

ok 100 numbers

Test #42:

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

input:

100 100 100
1111111111101111010111010110010010110000000010001110101100100100000110110011010100000010000010000111
1001110000100011000001011100010010001111001111101110010101101110011011100110011011011100000001110111
10010111111010101100101011001001100011101100111101101001110111110110111011101000111110...

output:

1373
1372
1373
1373
1373
1373
1372
1372
1371
1374
1374
1373
1373
1373
1373
1374
1375
1374
1375
1376
1375
1378
1378
1376
1377
1377
1377
1376
1374
1375
1375
1375
1374
1372
1372
1371
1372
1372
1372
1370
1371
1369
1369
1370
1370
1370
1372
1373
1373
1373
1374
1375
1376
1376
1376
1375
1375
1375
1375
1375
...

result:

ok 100 numbers

Test #43:

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

input:

200 200 200
11110010011100010000101001011001001001010111011010011101000100001001011011110011011111100101001101100001111101001110000010011000010110110101000000000111001100101110001010111111111111111110110101101010
000011110000100011001101110100101110001001100100101110111101001011110010100011001001011...

output:

5412
5412
5410
5409
5409
5410
5408
5408
5407
5406
5405
5406
5406
5410
5410
5409
5409
5408
5408
5407
5407
5407
5408
5406
5402
5402
5404
5402
5402
5401
5401
5402
5402
5402
5402
5402
5400
5399
5400
5400
5399
5399
5400
5399
5399
5399
5397
5397
5398
5396
5396
5398
5398
5397
5396
5396
5394
5394
5395
5393
...

result:

ok 200 numbers

Test #44:

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

input:

200 200 200
10000110100100100001011110110110101011111001100001101010011111101100110001101011110011010010111100000001010101110000101000101001111001100100011111001110100010001000010110111111110010111111001011001011
010001001010011111011110110001001100111011000001010101110101010110100110010110100000010...

output:

5421
5421
5421
5423
5423
5423
5424
5423
5421
5421
5421
5421
5421
5421
5421
5423
5424
5424
5424
5423
5423
5424
5424
5421
5422
5421
5421
5422
5421
5421
5420
5417
5418
5416
5416
5416
5416
5415
5416
5416
5416
5416
5416
5417
5418
5416
5417
5417
5417
5417
5416
5415
5415
5413
5412
5413
5415
5415
5415
5416
...

result:

ok 200 numbers

Test #45:

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

input:

200 200 200
00011111111001001001110001000110110111001000110110000000111111010110110010001110101010110101000100110100111011110111101111011001100010101110011111011010010100111001101010010011101010100011000010110111
000100110001011110111001100010000001111111101110111110011110010110010101100110011110100...

output:

5475
5477
5476
5476
5477
5477
5477
5476
5478
5478
5478
5480
5479
5480
5481
5481
5482
5482
5482
5481
5480
5481
5481
5480
5479
5478
5480
5481
5479
5480
5479
5477
5477
5477
5478
5479
5478
5477
5479
5480
5481
5481
5480
5482
5482
5481
5481
5483
5483
5485
5486
5486
5485
5485
5485
5484
5483
5479
5478
5478
...

result:

ok 200 numbers

Test #46:

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

input:

200 200 200
01010011000011101001011000001000100010100110011101101001101100110011100100011100110000010111111000010101000010101000101011101110000111010011101000000111101000111110110100010010100100111010100110000100
010101011000110010101010110011010011000001011111001000000111100111001000101111111111111...

output:

5434
5436
5438
5438
5438
5438
5440
5439
5439
5439
5438
5439
5439
5439
5440
5438
5438
5436
5436
5436
5437
5440
5440
5441
5442
5442
5441
5442
5443
5444
5445
5447
5448
5450
5447
5448
5448
5447
5447
5449
5450
5451
5453
5454
5453
5452
5455
5453
5453
5452
5453
5453
5452
5452
5453
5453
5450
5449
5449
5448
...

result:

ok 200 numbers

Test #47:

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

input:

200 200 200
00101010011010001001011110111110010000010011101000111111000101011010100110101001110001000000010011100000101010111011000000001111101000000010110001110011000111001110110100011110111000100010101110101101
110100101011010111011011100100010111000111011000110011101101111111011101011011010011000...

output:

5438
5437
5438
5437
5437
5437
5438
5435
5434
5434
5434
5434
5435
5438
5440
5441
5439
5438
5437
5434
5434
5434
5435
5434
5434
5434
5433
5435
5436
5437
5436
5434
5434
5432
5432
5432
5432
5431
5433
5433
5434
5432
5431
5429
5430
5430
5432
5432
5433
5433
5432
5433
5433
5432
5432
5431
5428
5429
5431
5432
...

result:

ok 200 numbers

Test #48:

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

input:

200 200 200
10110110111011101000100001011110001100111001110010010100110001111110101100101101101101100111101011000001000001010101000111011110111011001010110111111110111011111001101000010010010001101100000000011111
100100000000110111001100100101001001011011111000001000100100111110101011101010101000011...

output:

5386
5386
5385
5385
5384
5384
5383
5385
5385
5385
5384
5383
5384
5385
5384
5382
5382
5380
5381
5380
5380
5380
5380
5380
5384
5384
5385
5385
5386
5386
5388
5386
5385
5385
5384
5384
5385
5383
5383
5383
5383
5382
5381
5381
5380
5382
5382
5381
5381
5381
5383
5383
5384
5384
5385
5384
5383
5384
5383
5383
...

result:

ok 200 numbers

Test #49:

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

input:

200 200 200
11111111100011011000001110100000001101001100011101111110110010000111111111011111110101001100011010100101110101001010100101101111010111110101100100100000010101011011110111010010011101111101010000100110
110101111000111010101111110100001000111101011111100110001111100101111110000010000100101...

output:

5402
5401
5402
5404
5404
5406
5405
5405
5404
5403
5406
5405
5405
5406
5405
5406
5405
5405
5403
5401
5402
5403
5401
5401
5402
5400
5400
5402
5403
5403
5403
5404
5404
5403
5404
5401
5400
5399
5400
5399
5400
5400
5399
5397
5398
5398
5401
5402
5402
5403
5404
5404
5405
5405
5402
5400
5401
5402
5403
5403
...

result:

ok 200 numbers

Test #50:

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

input:

200 200 200
11000111011010111010100101000011110001100000001110010011001011100010111101011010011100011010100010110000111111011001101000011010111000100101111001110101100000101010011011011110000001100101111100001111
000100000011001010011101000011111110101010111010010101000111010101101111010111101100110...

output:

5350
5351
5349
5349
5348
5347
5345
5344
5344
5344
5346
5345
5344
5345
5345
5346
5348
5346
5347
5349
5349
5348
5348
5348
5347
5347
5346
5346
5344
5344
5344
5344
5344
5344
5345
5348
5348
5346
5346
5348
5349
5350
5350
5349
5349
5350
5352
5354
5353
5353
5353
5353
5354
5355
5357
5356
5356
5357
5356
5355
...

result:

ok 200 numbers

Test #51:

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

input:

200 200 200
00010000100010010010010001011111100011000111110111100001001011001010111111100110000100111101011010010001010110110110001110101011111011111100111011111001011110001101000111110111001110011000010100111101
010100101000100111001010000010110100100100011001101110101100001100001000100111011011111...

output:

5341
5342
5341
5340
5339
5341
5341
5341
5340
5339
5338
5338
5337
5338
5337
5337
5338
5338
5338
5339
5339
5338
5338
5339
5339
5341
5342
5343
5343
5344
5345
5346
5344
5344
5345
5345
5346
5347
5348
5348
5347
5348
5349
5350
5351
5351
5352
5351
5351
5350
5351
5352
5352
5353
5352
5352
5352
5352
5353
5353
...

result:

ok 200 numbers

Test #52:

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

input:

200 200 200
00000001001001111000010000000100011011011100000101110001111000110001110111001011001100000111011100100111000111100011000101011001101111010110110111001011111100110011101001011100110101011010000011100110
000101001001011011111011101010110110010100100010110101001011101101101011011100101000001...

output:

5451
5452
5451
5452
5453
5453
5454
5454
5454
5454
5454
5453
5454
5453
5454
5454
5453
5453
5454
5452
5453
5453
5453
5453
5450
5448
5446
5447
5448
5448
5446
5447
5445
5445
5446
5448
5448
5448
5448
5448
5444
5447
5448
5448
5448
5448
5448
5449
5450
5451
5451
5453
5455
5455
5454
5453
5453
5454
5452
5451
...

result:

ok 200 numbers

Test #53:

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

input:

1 200 200000
11111100001101111101000011001001010011001010001110011010100101100001110001000001111111010101011001100101110001111101111100000100001000010010111101100111100010011011001001000000011101000111110110111110
93 157
93 22
91 32
93 159
93 214
93 253
93 102
93 218
95 122
95 235
93 55
93 110
93 27...

output:

92
90
92
92
92
92
92
94
94
92
92
92
92
94
94
94
94
92
90
92
90
90
90
88
90
92
92
92
92
94
94
96
94
94
94
94
96
96
96
98
100
100
98
100
98
98
98
96
94
92
92
92
94
96
96
96
94
96
96
96
96
94
94
94
94
94
94
92
94
94
94
96
98
96
94
96
96
96
96
98
96
98
98
100
100
100
98
98
96
98
98
98
98
96
96
96
94
92
...

result:

ok 200000 numbers

Test #54:

score: 0
Accepted
time: 79ms
memory: 4576kb

input:

200 1 200000
0
1
1
0
0
1
1
1
0
0
0
1
1
0
1
0
0
0
1
0
1
1
1
0
1
0
0
0
0
0
0
1
1
1
1
0
0
0
1
0
1
0
0
0
1
1
1
1
1
1
1
1
0
0
0
1
0
0
0
1
1
1
0
1
1
1
1
0
0
1
0
0
0
1
0
1
1
0
0
1
1
1
1
1
1
0
1
0
0
1
0
0
1
1
1
1
0
1
1
0
0
0
1
1
1
0
0
1
0
1
0
1
0
0
1
0
0
1
0
1
0
0
0
0
0
0
1
1
0
1
0
0
0
1
0
1
0
1
1
0
0
0
1
1...

output:

104
104
104
106
108
106
106
106
106
106
108
106
104
102
102
104
104
102
102
104
104
102
102
100
102
100
98
98
100
100
98
96
94
96
94
94
92
94
92
94
96
96
96
96
96
98
98
98
96
98
98
100
102
100
100
98
100
98
98
98
96
94
96
96
98
98
96
96
96
96
98
96
94
96
96
96
94
94
92
94
96
96
94
94
96
96
96
96
96
...

result:

ok 200000 numbers

Test #55:

score: 0
Accepted
time: 2403ms
memory: 4212kb

input:

20 200 200000
11001010010000000000011101011001011110000001101000111101110011110100100101011000110110010000101010100010000100000100001000001100100001111101101111101110111001001101000010101111011101111010100001111001
0000101011001010110010000010110011001010000111111010010100101100011000110000001011011...

output:

613
614
615
615
615
615
618
618
617
618
621
623
624
625
623
623
623
623
622
620
621
622
623
623
624
625
624
625
625
625
625
625
627
626
627
627
628
630
630
630
631
631
631
631
633
633
632
632
632
631
633
631
630
630
630
631
632
630
627
627
629
628
628
628
625
624
624
624
623
624
624
623
623
623
623
...

result:

ok 200000 numbers

Test #56:

score: 0
Accepted
time: 579ms
memory: 4516kb

input:

200 20 200000
01110011110011111001
00010000010010110101
11101000101111111100
10010010110100101001
10111111110101011110
11101010011001100000
11011011001011001010
00110110101010001010
00101111001011101001
01001001011100101001
01011010100100111110
01001001101010010000
00111100111101001101
0100001111001...

output:

589
590
590
589
589
590
587
589
587
588
587
587
586
586
587
588
588
588
589
590
590
588
588
588
589
586
584
584
582
581
585
588
588
588
587
587
586
585
585
586
587
586
587
588
587
587
586
586
587
586
586
586
585
586
585
585
584
584
584
582
583
582
584
585
585
586
586
588
588
589
589
588
589
590
590
...

result:

ok 200000 numbers

Test #57:

score: -100
Time Limit Exceeded

input:

200 200 200000
10110011111010111100010011011001000011011101001110111010110100001000101010100100011110101010001101101010110000110011000101011101001111010001111000010111111100010110010010100000001011100001100001100111
110011101001100101000010111111101110111101011110011000000000110011011110100010100110...

output:

5329
5328
5328
5328
5327
5328
5328
5327
5329
5328
5327
5327
5328
5328
5329
5327
5326
5326
5326
5326
5326
5327
5328
5327
5328
5328
5328
5327
5327
5328
5328
5328
5327
5327
5329
5328
5327
5328
5329
5328
5328
5330
5329
5327
5326
5326
5326
5328
5328
5327
5328
5327
5327
5326
5325
5326
5326
5329
5331
5330
...

result: