QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#619832#5267. Bricks in the WallMCdycAC ✓329ms155828kbC++203.6kb2024-10-07 15:34:322024-10-07 15:34:35

Judging History

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

  • [2024-10-07 15:34:35]
  • 评测
  • 测评结果:AC
  • 用时:329ms
  • 内存:155828kb
  • [2024-10-07 15:34:32]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

int solve()
{
    int n, m;
    cin >> n >> m;
    vector<string> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    vector<vector<pair<int, int>>> x(n, vector<pair<int, int>>(m));
    auto y = x;
    priority_queue<int> x_mx, y_mx;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (a[i][j] == '.')
            {
                int r = j;
                while (r < m && a[i][r] == '.')
                {
                    r++;
                }
                x_mx.emplace(r - j);
                r--;
                for (int l = j; l <= r; l++)
                {
                    x[i][l].first = l - j;
                    x[i][l].second = r - l;
                }
                j = r;
            }
        }
    }
    for (int j = 0; j < m; j++)
    {
        for (int i = 0; i < n; i++)
        {
            if (a[i][j] == '.')
            {
                int r = i;
                while (r < n && a[r][j] == '.')
                {
                    r++;
                }
                y_mx.emplace(r - i);
                r--;
                for (int l = i; l <= r; l++)
                {
                    y[l][j].first = l - i;
                    y[l][j].second = r - l;
                }
                i = r;
            }
        }
    }
    x_mx.emplace(0), x_mx.emplace(0);
    y_mx.emplace(0), y_mx.emplace(0);

    int ans = 0;
    {
        int t = 0;
        t += x_mx.top();
        x_mx.pop();
        t += x_mx.top();
        ans = max(ans, t);
    }
    {
        int t = 0;
        t += y_mx.top();
        y_mx.pop();
        t += y_mx.top();
        ans = max(ans, t);
    }
    priority_queue<int> q;
    q.emplace(0);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (a[i][j] == '.')
            {
                ans = max(ans, y[i][j].second + q.top() + 1);
                ans = max(ans, y[i][j].second + 1 + x[i][j].first);
                q.push(x[i][j].first + 1);
            }
        }
    }
    while (!q.empty())
    {
        q.pop();
    }
    q.emplace(0);
    for (int j = m - 1; j >= 0; j--)
    {
        for (int i = 0; i < n; i++)
        {
            if (a[i][j] == '.')
            {
                ans = max(ans, x[i][j].first + q.top() + 1);
                ans = max(ans, y[i][j].first + 1 + x[i][j].first);
                q.push(y[i][j].first + 1);
            }
        }
    }
    while (!q.empty())
    {
        q.pop();
    }
    q.emplace(0);
    for (int i = n - 1; i >= 0; i--)
    {
        for (int j = m - 1; j >= 0; j--)
        {
            if (a[i][j] == '.')
            {
                ans = max(ans, y[i][j].first + q.top() + 1);
                ans = max(ans, y[i][j].first + 1 + x[i][j].second);
                q.push(x[i][j].second + 1);
            }
        }
    }
    while (!q.empty())
    {
        q.pop();
    }
    q.emplace(0);
    for (int j = 0; j < m; j++)
    {
        for (int i = n - 1; i >= 0; i--)
        {
            if (a[i][j] == '.')
            {
                ans = max(ans, x[i][j].second + q.top() + 1);
                ans = max(ans, x[i][j].second + 1 + y[i][j].second);
                q.push(y[i][j].second + 1);
            }
        }
    }

    cout << ans << "\n";
    return 0;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int test = 1;
    cin >> test;
    while (test--)
    {
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3620kb

input:

5
2 2
..
..
4 5
###.#
#....
.##.#
#.#.#
2 1
.
.
2 3
###
#.#
5 4
##.#
..#.
#.#.
....
#.##

output:

4
6
2
1
7

result:

ok 5 number(s): "4 6 2 1 7"

Test #2:

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

input:

10000
1 6
..#..#
5 7
#..##.#
..###.#
.####..
.##.##.
..#.#.#
1 7
#.####.
10 5
##..#
###.#
....#
#.#..
##.##
###.#
#....
##.##
...##
.....
1 2
.#
1 3
##.
7 6
####..
#####.
#...#.
..#..#
..##.#
##.#..
#..##.
5 4
..##
..#.
..##
..#.
##.#
5 6
.##..#
.#....
##.#.#
#..###
##....
1 6
.#.###
1 2
##
5 5
##.....

output:

4
7
2
9
1
1
6
8
8
2
0
6
3
4
4
8
12
4
10
12
8
5
8
3
5
8
1
6
8
4
6
12
7
4
6
2
5
6
3
10
5
5
8
3
4
4
7
8
4
8
6
6
6
4
4
13
3
3
7
7
2
8
3
6
6
4
5
6
11
6
6
6
6
6
9
1
7
7
8
3
7
3
8
10
3
5
4
7
9
5
2
8
6
4
6
2
7
4
2
5
7
10
4
8
8
8
9
8
8
6
2
9
3
9
10
7
4
6
7
8
5
6
7
9
4
8
11
5
6
4
9
2
8
2
3
8
6
7
11
7
6
12
6
1...

result:

ok 10000 numbers

Test #3:

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

input:

10000
1 5
#####
9 5
##..#
##.##
.####
#.###
###.#
..#.#
#####
####.
#####
10 9
.########
#.#######
##.#..###
########.
#######.#
########.
#########
#########
#########
###.#####
5 2
##
##
##
##
.#
3 9
#########
#########
#######.#
8 8
########
.#####.#
########
.#######
#######.
###.#..#
#.######
....

output:

0
4
3
1
1
3
0
0
1
3
2
1
2
3
1
3
3
2
2
2
3
2
3
2
5
0
0
1
1
4
0
2
0
1
3
4
0
2
4
3
2
2
1
2
2
2
2
3
3
2
2
2
1
1
2
2
1
2
4
3
1
1
3
2
5
0
3
3
0
4
4
1
3
0
1
2
1
0
2
1
1
1
2
4
2
0
3
0
2
2
2
2
2
2
1
1
2
2
2
1
3
3
2
2
0
0
2
2
1
1
4
1
2
3
0
2
1
2
0
2
4
3
1
2
0
2
1
3
3
3
1
3
4
3
4
2
0
3
3
5
2
0
0
0
2
6
2
2
2
0
...

result:

ok 10000 numbers

Test #4:

score: 0
Accepted
time: 14ms
memory: 3604kb

input:

10000
9 6
######
######
.#####
######
######
######
######
#####.
######
9 7
#######
#######
#######
#######
#######
#######
#######
#######
#######
2 5
#####
#####
7 5
####.
#####
.####
#####
#####
#####
#####
1 4
####
9 6
######
######
######
######
######
######
######
######
######
10 8
########...

output:

2
0
0
2
0
0
2
2
1
2
0
0
1
1
2
0
0
2
0
0
1
2
2
0
0
1
1
2
2
2
2
0
2
2
1
0
0
1
0
2
1
1
1
2
1
3
3
2
0
1
3
0
2
2
1
2
2
1
0
0
2
1
2
2
2
3
1
0
2
1
0
1
1
2
1
1
0
1
3
0
0
0
1
0
1
0
2
2
1
2
0
0
3
0
0
0
0
2
0
2
1
0
0
2
2
1
0
0
2
0
1
0
2
2
1
1
1
0
2
2
2
0
0
0
0
2
1
2
0
2
2
0
0
0
0
2
2
0
0
0
0
2
0
1
2
1
1
2
0
3
...

result:

ok 10000 numbers

Test #5:

score: 0
Accepted
time: 47ms
memory: 3704kb

input:

10000
5 4
....
....
....
....
....
5 2
..
.#
..
..
..
1 8
...#....
8 10
.#..#...#.
.#........
...#......
..........
#.........
.##.......
..........
..........
2 10
..........
........#.
7 6
......
......
......
......
......
...#..
......
2 2
.#
..
9 1
.
.
.
.
.
.
.
.
.
5 1
.
.
.
.
.
9 5
.....
.......

output:

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

result:

ok 10000 numbers

Test #6:

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

input:

1000
6 16
.##..#.##.######
#.##.###...#..##
##.#####.##.#.##
.##..#.#.#..#...
..#..#.#.#.#....
#.#.#..#.#.#.#.#
8 17
##..#...######.#.
..####.######..#.
###.###.#..#.#.##
..#.#.##..#.#.##.
##.#.#.##.#....##
#..###..#.#.#....
.#.....#...#....#
.#..#.##.##...##.
16 25
.##.###.####.##...#.#####
#..##.#...

output:

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

result:

ok 1000 numbers

Test #7:

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

input:

1000
3 185
#...#..##.###.##..#######..##..#.##.##..####.##.......###.##..##.....###.##..#####....######.####.##.###.###.#....###...#.....##.#....#....#..##..#.####.#.##.#.####..#...#####.#.#.##.#.
.#.##.####.#.##..#.#.######....#..##..##..#.#.########.#.##.#.####.#...###......#.#..#.###...#...#.###....

output:

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

result:

ok 1000 numbers

Test #8:

score: 0
Accepted
time: 36ms
memory: 3908kb

input:

1000
40 2
..
##
.#
..
..
..
..
..
##
.#
..
..
..
..
..
##
#.
#.
.#
..
##
##
..
.#
##
##
##
#.
..
.#
.#
#.
.#
..
##
.#
..
.#
##
#.
19 1
#
.
#
#
#
#
.
#
#
.
#
#
.
#
.
.
#
.
#
24 4
.#..
.##.
#.##
#.##
##..
.###
##.#
##..
#...
#..#
###.
..#.
####
.#.#
.###
#.##
##.#
##.#
.#..
###.
.#.#
....
....
.###
12...

output:

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

result:

ok 1000 numbers

Test #9:

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

input:

100
2 45
#.###..###.#..#..#...#####.##..#.....##.##.#.
..#..#.#.###.######.#.###...####.#...#.###.##
4 63
.#...####...####.####..#.#...#.###.###...##...#..#.#...##...#..
#.##..##.#.####.#....#.#...########.#.######..##.##.#..###.##..
#..##.#...##.#.#..###..#..#.###.#...........##.#.####..##.#####
.#...

output:

8
16
15
21
22
12
26
19
24
15
21
20
14
19
16
17
1
19
22
18
20
29
18
21
22
16
16
22
27
27
19
24
13
13
18
14
12
15
19
20
18
21
24
20
14
15
17
20
20
22
17
16
26
20
26
20
18
16
23
24
13
18
17
22
18
13
23
23
23
17
17
22
25
16
21
13
13
18
17
16
24
26
17
23
19
6
8
25
20
14
21
21
21
22
15
17
16
15
15
18

result:

ok 100 numbers

Test #10:

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

input:

100
2 72
##.###########.###.############.#########.##########.###########.#######
#...###########.#.##.############.#.######################.##.###.####..
75 58
####.##########.###.#################.#####.##############
#######..###############.######.############.#############
#####################...

output:

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

result:

ok 100 numbers

Test #11:

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

input:

100
43 93
#######################################################################################.#####
#############################################################################################
#############################################################################################
########...

output:

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

result:

ok 100 numbers

Test #12:

score: 0
Accepted
time: 4ms
memory: 4360kb

input:

10
41 499
##########################################.#####################################.#.####.################################.#####.############.#####.######################.#######.###########.######.######################.#.##############################.####.#.#######.###.###########...###.....

output:

9
6
8
9
8
4
8
6
6
6

result:

ok 10 numbers

Test #13:

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

input:

10
41 877
#.##########....##..##.#..###...#...#.###.#.#..#.#.#..##..#..#.##.#.#.##.......#..####..##.#.####.###.##.#...#..#..###...##.#.###.#.#.....###..#.###.#..#....#...#..#.#.##.#.##..#.#.#..##.#...#.#...#.##...###.###.....#.###.#..##.####..###.#.####.###......#....#.##.###.#.###.#..##....####......

output:

28
26
16
27
28
36
21
30
16
23

result:

ok 10 numbers

Test #14:

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

input:

10
859 68
###.##############.##########..#########.##..#...####.##.#.#########
.#.##.#################################################.#######.####
.####.###############..##########.###########.######################
####.#####################.#.##.##.#########.##############.########
########.#####...

output:

8
8
10
6
7
10
7
6
10
9

result:

ok 10 numbers

Test #15:

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

input:

10
963 50
###.##...#....#..#..#...#.##..#.###...#.#..###...#
...####...#..#.##.#..#....###.#.#.##....#.#.##.#..
#....#.#......#######.##.###.###..###.#.#....##..#
.####....#####..#.#.#.#.###.##.#....#...#..###.##.
##..##...#...#.#..#....#.#.#.#.#.##..#.#.#..#..##.
.####.###.....#......####..##.........

output:

27
16
22
20
24
22
18
27
28
31

result:

ok 10 numbers

Test #16:

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

input:

10
23 107
#.####.####.###########..#############.####.#############################.#######.#######.########.########
####.###################.#######.##################.#####.###################.#.###########################
#######.##.#############################...##############.###########.###....

output:

84
173
187
212
57
46
172
39
8
18

result:

ok 10 numbers

Test #17:

score: 0
Accepted
time: 27ms
memory: 5152kb

input:

10
55 78
...#.##.#####....##.##.#...#.#...###.###..#..#.##..##...####.....#.##.#....#.#
.###.#..#.#.#####.#..######....#...#...#..###..#.######..####.##.#..##...#...#
.####...#.##.....#.#.#..#...###.#........##....####.##.##.#..###..##.####....#
#......##.#.......#..##.#.###..#.#......###.#..#..#.##...

output:

91
215
209
239
115
44
140
166
301
446

result:

ok 10 numbers

Test #18:

score: 0
Accepted
time: 52ms
memory: 5364kb

input:

10
3 2515
#..##..#..#..#..#...##...###...###.##..#..###.##..##.##.#.######..##.##..##.###.#....................................................................................................................................................................................................................

output:

4942
402
12899
15672
5915
2113
15630
15104
778
306

result:

ok 10 numbers

Test #19:

score: 0
Accepted
time: 74ms
memory: 6160kb

input:

10
9644 5
##...
####.
#..##
##..#
#...#
.#.#.
..#..
.#..#
#.#.#
..##.
#...#
.#.#.
#..#.
#..#.
##...
.###.
#.##.
##.#.
.#...
###..
####.
.....
.##..
#.##.
.##..
.....
.###.
..#..
...#.
#.#..
...#.
##.#.
...#.
...#.
##...
.###.
.....
.#.#.
.#...
..##.
##.#.
#..#.
###..
#....
#....
#.#..
..#..
##...
.....

output:

18955
9043
17912
8479
12922
14983
15186
15888
15222
6580

result:

ok 10 numbers

Test #20:

score: 0
Accepted
time: 49ms
memory: 5624kb

input:

10
9485 6
......
..#..#
......
##....
......
..##..
.....#
...#..
....#.
...#..
......
....#.
......
......
......
.#....
......
.#.#.#
.#..#.
....#.
#..#..
....#.
#.....
.##...
......
.#....
......
#....#
......
..#...
......
......
......
.#....
..#...
.#....
#.....
.#.#..
......
##.#..
.#....
......

output:

159
172
137
139
160
140
170
152
85
136

result:

ok 10 numbers

Test #21:

score: 0
Accepted
time: 42ms
memory: 5316kb

input:

10
3233 5
.....
.....
.....
.....
.....
.....
.....
..#..
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
..#..
.....
.....
.....
.....
.....
.....
.....
.....
.....
.#...
.....
.....
.....
.....
.....

output:

909
1104
883
1415
414
508
1035
877
986
1050

result:

ok 10 numbers

Test #22:

score: 0
Accepted
time: 241ms
memory: 25520kb

input:

1
1000 1000
........#.#....#...............#....#.#.............#.#........#......#.......#...#....#...........#.............#...#............#..................##......#..#.................................##.....###......#..........#..............#.#.................#.......#...........#..............

output:

213

result:

ok 1 number(s): "213"

Test #23:

score: 0
Accepted
time: 214ms
memory: 37212kb

input:

1
100000 10
..........
.......#..
.......#..
.........#
#.....#...
........#.
##...#....
.#........
......#...
..#..#...#
........#.
...#......
..........
.#.......#
.#........
..........
..........
.........#
..........
..........
....#.....
.......#..
.#........
..........
.....#..##
......#..#
.....

output:

195

result:

ok 1 number(s): "195"

Test #24:

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

input:

1
10 10000
#.......#.........#........#...............#......#......#..#...........................................#.#.#..#......#............#............#.....#........#.#...#....#...........#..#...............#...#.....#.#.#...#..#............#.#....#...#.................#....#..#......#............

output:

238

result:

ok 1 number(s): "238"

Test #25:

score: 0
Accepted
time: 233ms
memory: 155184kb

input:

1
1000000 1
#
.
.
.
.
.
.
.
.
.
.
#
.
.
.
.
.
.
.
#
.
.
#
.
.
.
.
.
.
.
.
.
.
.
#
.
#
.
.
.
.
.
.
.
.
.
.
.
.
.
.
#
.
.
.
.
.
.
.
.
.
.
.
.
#
.
.
#
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
#
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
#
.
.
.
.
.
#
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...

output:

211

result:

ok 1 number(s): "211"

Test #26:

score: 0
Accepted
time: 169ms
memory: 31104kb

input:

1
1 1000000
..#.........#.........................#............................#..................#......#........##................#..#..###...#.#.#......#...#........###.....................#...................................................#..............#....................###.##.................

output:

214

result:

ok 1 number(s): "214"

Test #27:

score: 0
Accepted
time: 81ms
memory: 143860kb

input:

1
1000000 1
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
...

output:

0

result:

ok 1 number(s): "0"

Test #28:

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

input:

1
1 1000000
################################################################################################################################################################################################################################################################################################...

output:

0

result:

ok 1 number(s): "0"

Test #29:

score: 0
Accepted
time: 121ms
memory: 23972kb

input:

1
1000 1000
....####...#..######...#...#..##..###..##..#####..#...##.#####.#...####.#.#..#..##.....#..#.#..#.#....##....##.#..#.###...#..#.########..#..#.#.###.##....#...#.#..#.#...####..#..##..####.....##.#.##.##...##..#.###....#....#....#.#.#...#....####......##....###..####.##......#..###..#........

output:

1223

result:

ok 1 number(s): "1223"

Test #30:

score: 0
Accepted
time: 126ms
memory: 24056kb

input:

1
1000 1000
..##...#..##.#....#.##.#....#...#...#....#######.####.##.###...#.###.#.####..#.#.##.#########.#.#####.#...#..###.#.#.#.#.##...#....#.######...#####.#....##..##.#....###..#.#....#.#.#.#.#.#.##.##...#.##...#..####..#..##....#.##.#.#.#.#.##.###..#####.##..#.####.#.##.#.####.##...##.##.##.#....

output:

1116

result:

ok 1 number(s): "1116"

Test #31:

score: 0
Accepted
time: 113ms
memory: 23968kb

input:

1
1000 1000
..###..#..#.#...#####.#..#.#.###..###.#.##.....##..#####.#..#...##########..###.#.#...######..####..###.#..####.#..##.####...####.#.#..#.#...##.#.##.#.#...####..#..#....#..#..####....#..##.#.#.#...#######...##..####.#######.#..###..#..###.#..#####....##.######...#..#...###.#..#...##.##.....

output:

1153

result:

ok 1 number(s): "1153"

Test #32:

score: 0
Accepted
time: 133ms
memory: 24056kb

input:

1
1000 1000
.#..####..#.####......#.##.####...#.####....#..###....#.#.##.#..#..#..##..#.##..#.#....##.##.###.###.#.#..##.#...#.#..#.#....#.#.##..#.#.##...###.##....#....##..########.##.###..#..#.#..#.......#..##..#.#.##.....#.##..#.#.##.#.###.###.##.#..####..##...#.#..#####.####....###...#.#...#.##....

output:

959

result:

ok 1 number(s): "959"

Test #33:

score: 0
Accepted
time: 329ms
memory: 25308kb

input:

1
1000 1000
...................................................................................................................................................................................................................................................................................................

output:

2000

result:

ok 1 number(s): "2000"

Test #34:

score: 0
Accepted
time: 266ms
memory: 34720kb

input:

1
100000 10
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
.....

output:

200000

result:

ok 1 number(s): "200000"

Test #35:

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

input:

1
10 10000
....................................................................................................................................................................................................................................................................................................

output:

20000

result:

ok 1 number(s): "20000"

Test #36:

score: 0
Accepted
time: 250ms
memory: 155828kb

input:

1
1000000 1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...

output:

1000000

result:

ok 1 number(s): "1000000"

Test #37:

score: 0
Accepted
time: 198ms
memory: 31676kb

input:

1
1 1000000
...................................................................................................................................................................................................................................................................................................

output:

1000000

result:

ok 1 number(s): "1000000"

Test #38:

score: 0
Accepted
time: 254ms
memory: 155440kb

input:

1
1000000 1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...

output:

83540

result:

ok 1 number(s): "83540"

Test #39:

score: 0
Accepted
time: 250ms
memory: 31720kb

input:

1
1 1000000
...................................................................................................................................................................................................................................................................................................

output:

88303

result:

ok 1 number(s): "88303"

Test #40:

score: 0
Accepted
time: 326ms
memory: 26184kb

input:

1
1000 1000
...........................................................................................#.......................................................................................................................................................................................................

output:

2000

result:

ok 1 number(s): "2000"

Test #41:

score: 0
Accepted
time: 273ms
memory: 35416kb

input:

1
100000 10
..........
..........
..........
..........
..........
..........
..........
..........
.........#
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
.....

output:

15559

result:

ok 1 number(s): "15559"

Test #42:

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

input:

1
10 10000
.............................................................................................................................................................................................................#......................................................................................

output:

7395

result:

ok 1 number(s): "7395"

Test #43:

score: 0
Accepted
time: 222ms
memory: 79784kb

input:

1
500000 2
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
....

output:

1000000

result:

ok 1 number(s): "1000000"

Test #44:

score: 0
Accepted
time: 220ms
memory: 29656kb

input:

1
2 500000
....................................................................................................................................................................................................................................................................................................

output:

1000000

result:

ok 1 number(s): "1000000"

Test #45:

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

input:

1
500000 2
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
....

output:

360154

result:

ok 1 number(s): "360154"

Test #46:

score: 0
Accepted
time: 239ms
memory: 29892kb

input:

1
2 500000
....................................................................................................................................................................................................................................................................................................

output:

387653

result:

ok 1 number(s): "387653"

Test #47:

score: 0
Accepted
time: 245ms
memory: 80356kb

input:

1
500000 2
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
....

output:

90498

result:

ok 1 number(s): "90498"

Test #48:

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

input:

1
2 500000
....................................................................................................................................................................................................................................................................................................

output:

81255

result:

ok 1 number(s): "81255"

Test #49:

score: 0
Accepted
time: 242ms
memory: 81848kb

input:

1
500000 2
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
....

output:

15623

result:

ok 1 number(s): "15623"

Test #50:

score: 0
Accepted
time: 252ms
memory: 29648kb

input:

1
2 500000
...................................................................................................................................................................................................................................................................................#................

output:

15179

result:

ok 1 number(s): "15179"

Test #51:

score: 0
Accepted
time: 218ms
memory: 79912kb

input:

1
500000 2
..
..
..
..
..
..
..
..
..
..
..
#.
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
.#
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
.#
..
..
..
....

output:

1769

result:

ok 1 number(s): "1769"

Test #52:

score: 0
Accepted
time: 229ms
memory: 29648kb

input:

1
2 500000
.........................................................................................................#..........................................................................................................................#........................#......................................

output:

2031

result:

ok 1 number(s): "2031"

Test #53:

score: 0
Accepted
time: 204ms
memory: 83000kb

input:

1
500000 2
..
..
..
..
..
..
..
..
..
##
..
..
.#
..
..
..
..
..
..
..
..
..
#.
.#
..
..
..
.#
#.
..
..
..
..
#.
..
..
..
..
..
..
..
..
..
..
..
..
.#
#.
#.
..
..
..
..
..
#.
..
..
..
..
..
..
#.
..
..
..
..
..
..
.#
.#
..
..
.#
..
.#
#.
..
..
..
..
..
..
..
..
..
..
..
..
.#
..
..
..
..
.#
..
..
....

output:

243

result:

ok 1 number(s): "243"

Test #54:

score: 0
Accepted
time: 186ms
memory: 29940kb

input:

1
2 500000
...##.........#..........................#.................#..#................................#..#...............##.............#.#........#...........#...........#..........#......#..............................#.............#.........#.##..............#..........#...#..............#......

output:

221

result:

ok 1 number(s): "221"

Test #55:

score: 0
Accepted
time: 75ms
memory: 74840kb

input:

1
500000 2
##
##
##
##
##
##
#.
##
##
##
##
##
##
##
##
##
#.
##
##
##
##
##
##
##
#.
##
##
##
##
.#
##
#.
##
##
##
##
##
##
##
##
##
##
##
##
##
##
##
.#
##
##
##
##
##
#.
##
##
.#
##
##
##
##
##
##
##
##
##
.#
##
##
##
##
#.
##
##
##
##
##
#.
#.
##
##
##
##
##
##
##
##
##
##
##
##
#.
##
##
##
##
#...

output:

12

result:

ok 1 number(s): "12"

Test #56:

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

input:

1
2 500000
###############.###########.###########.##############.#######.#########################.##################################.#########.###.#.#.###########.#######.#.########.##.#############..#####.########.########.#####.#####.##.#.###############.########.###.####.############.##########...

output:

10

result:

ok 1 number(s): "10"