QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#673778#5267. Bricks in the WallIllusionaryDominance#AC ✓161ms210376kbC++202.4kb2024-10-25 10:05:042024-10-25 10:05:05

Judging History

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

  • [2024-10-25 10:05:05]
  • 评测
  • 测评结果:AC
  • 用时:161ms
  • 内存:210376kb
  • [2024-10-25 10:05:04]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using namespace std;
using ll=long long;
#define all(x) (x).begin(), (x).end()

int cal_row(string s)
{
    int r=0, tmp=0;
    for(int j=1;j<s.size();++j) 
    {
        if(s[j]=='#') r=max(r, tmp), tmp=0;
        else ++tmp, r=max(r, tmp);
    }
    return r;
}

int cal1(vector<string> a, int n, int m)
{
    vector<int> num;
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)if(a[i][j]=='.')
        {
            int r=j;
            while(r+1<=m&&a[i][r+1]=='.') ++r;
            num.push_back(r-j+1);
            j=r;
        }
    }
    sort(all(num)); reverse(all(num));
    
    // for(auto x : num) cerr<<x<<" ";cerr<<"\n";
    
    int sum=0;
    for(int i=0; i<=1 && i<num.size(); ++i) sum+=num[i];
    return sum;
}

int cal2(vector<string> a, int n, int m)
{
    vector pre(n+2, vector<int>(m+2)), suf=pre;
    for(int j=1;j<=m;++j)
    {
        int tmp=0;
        for(int i=1;i<=n;++i)
        {
            pre[i][j]=pre[i-1][j];
            if(a[i][j]=='.') ++tmp, pre[i][j]=max(pre[i][j], tmp);
            else tmp=0;
        }
    }
    
    for(int j=1;j<=m;++j)
    {
        int tmp=0;
        for(int i=n;i;--i)
        {
            if(i<n) suf[i][j]=suf[i+1][j];
            if(a[i][j]=='.') ++tmp, suf[i][j]=max(suf[i][j], tmp);
            else tmp=0;
        }
    }
    
    for(int j=1;j<=m;++j) for(int i=1;i<=n;++i) pre[i][j]=max(pre[i][j], pre[i][j-1]);
    for(int j=m-1; j; --j) for(int i=1;i<=n;++i) suf[i][j]=max(suf[i][j], suf[i][j+1]);
    
    int sum=0;
    
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j) if(a[i][j]=='.')
        {
            int r=j;
            while(r+1<=m && a[i][r+1]=='.') ++r;
            
            sum=max(sum, r-j+1+max({pre[i-1][m], pre[n][j-1], suf[i+1][1], suf[1][r+1]}));
            
            j=r;
        }
        
    }
    
    return sum;
}

void solve()
{
    int n, m;
    cin>>n>>m;
    vector<string> s(n+1);
    for(int i=1;i<=n;++i) cin>>s[i], s[i]=" "+s[i];
    
    vector<string> t(m+1, string(n+1, ' '));
    for(int j=1;j<=m;++j) for(int i=1;i<=n;++i) t[j][i]=s[i][j];
    
    cout << max({cal1(s, n, m), cal1(t, m, n), cal2(s, n, m), cal2(t, m, n)}) << "\n";
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
    
    int T;
    cin>>T;
    while(T--) solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 37ms
memory: 3560kb

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: 25ms
memory: 3572kb

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: 22ms
memory: 3544kb

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: 21ms
memory: 3844kb

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: 20ms
memory: 3628kb

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: 3856kb

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: 31ms
memory: 3836kb

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: 15ms
memory: 3864kb

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: 8ms
memory: 4016kb

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: 6ms
memory: 3732kb

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: 5ms
memory: 4176kb

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: 11ms
memory: 4548kb

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: 8ms
memory: 4456kb

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: 13ms
memory: 4664kb

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: 3ms
memory: 4380kb

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: 15ms
memory: 4448kb

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: 7ms
memory: 5544kb

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: 17ms
memory: 5664kb

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: 20ms
memory: 5648kb

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: 13ms
memory: 5320kb

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: 40ms
memory: 17324kb

input:

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

output:

213

result:

ok 1 number(s): "213"

Test #23:

score: 0
Accepted
time: 41ms
memory: 31776kb

input:

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

output:

195

result:

ok 1 number(s): "195"

Test #24:

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

input:

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

output:

238

result:

ok 1 number(s): "238"

Test #25:

score: 0
Accepted
time: 161ms
memory: 210336kb

input:

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

output:

211

result:

ok 1 number(s): "211"

Test #26:

score: 0
Accepted
time: 131ms
memory: 209240kb

input:

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

output:

214

result:

ok 1 number(s): "214"

Test #27:

score: 0
Accepted
time: 137ms
memory: 210376kb

input:

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

output:

0

result:

ok 1 number(s): "0"

Test #28:

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

input:

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

output:

0

result:

ok 1 number(s): "0"

Test #29:

score: 0
Accepted
time: 61ms
memory: 17352kb

input:

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

output:

1223

result:

ok 1 number(s): "1223"

Test #30:

score: 0
Accepted
time: 69ms
memory: 17332kb

input:

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

output:

1116

result:

ok 1 number(s): "1116"

Test #31:

score: 0
Accepted
time: 65ms
memory: 17316kb

input:

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

output:

1153

result:

ok 1 number(s): "1153"

Test #32:

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

input:

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

output:

959

result:

ok 1 number(s): "959"

Test #33:

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

input:

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

output:

2000

result:

ok 1 number(s): "2000"

Test #34:

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

input:

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

output:

200000

result:

ok 1 number(s): "200000"

Test #35:

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

input:

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

output:

20000

result:

ok 1 number(s): "20000"

Test #36:

score: 0
Accepted
time: 130ms
memory: 210188kb

input:

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

output:

1000000

result:

ok 1 number(s): "1000000"

Test #37:

score: 0
Accepted
time: 124ms
memory: 209248kb

input:

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

output:

1000000

result:

ok 1 number(s): "1000000"

Test #38:

score: 0
Accepted
time: 147ms
memory: 210252kb

input:

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

output:

83540

result:

ok 1 number(s): "83540"

Test #39:

score: 0
Accepted
time: 112ms
memory: 209376kb

input:

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

output:

88303

result:

ok 1 number(s): "88303"

Test #40:

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

input:

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

output:

2000

result:

ok 1 number(s): "2000"

Test #41:

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

input:

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

output:

15559

result:

ok 1 number(s): "15559"

Test #42:

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

input:

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

output:

7395

result:

ok 1 number(s): "7395"

Test #43:

score: 0
Accepted
time: 87ms
memory: 107716kb

input:

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

output:

1000000

result:

ok 1 number(s): "1000000"

Test #44:

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

input:

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

output:

1000000

result:

ok 1 number(s): "1000000"

Test #45:

score: 0
Accepted
time: 90ms
memory: 107892kb

input:

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

output:

360154

result:

ok 1 number(s): "360154"

Test #46:

score: 0
Accepted
time: 64ms
memory: 107568kb

input:

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

output:

387653

result:

ok 1 number(s): "387653"

Test #47:

score: 0
Accepted
time: 92ms
memory: 107912kb

input:

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

output:

90498

result:

ok 1 number(s): "90498"

Test #48:

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

input:

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

output:

81255

result:

ok 1 number(s): "81255"

Test #49:

score: 0
Accepted
time: 88ms
memory: 107708kb

input:

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

output:

15623

result:

ok 1 number(s): "15623"

Test #50:

score: 0
Accepted
time: 71ms
memory: 107644kb

input:

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

output:

15179

result:

ok 1 number(s): "15179"

Test #51:

score: 0
Accepted
time: 72ms
memory: 107788kb

input:

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

output:

1769

result:

ok 1 number(s): "1769"

Test #52:

score: 0
Accepted
time: 73ms
memory: 107604kb

input:

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

output:

2031

result:

ok 1 number(s): "2031"

Test #53:

score: 0
Accepted
time: 82ms
memory: 107900kb

input:

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

output:

243

result:

ok 1 number(s): "243"

Test #54:

score: 0
Accepted
time: 77ms
memory: 107776kb

input:

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

output:

221

result:

ok 1 number(s): "221"

Test #55:

score: 0
Accepted
time: 80ms
memory: 107488kb

input:

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

output:

12

result:

ok 1 number(s): "12"

Test #56:

score: 0
Accepted
time: 66ms
memory: 107440kb

input:

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

output:

10

result:

ok 1 number(s): "10"