QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#64857#1437. The Destruction of the Crystalsgyh20AC ✓209ms12620kbC++141.5kb2022-11-25 19:28:422022-11-25 19:28:43

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-25 19:28:43]
  • 评测
  • 测评结果:AC
  • 用时:209ms
  • 内存:12620kb
  • [2022-11-25 19:28:42]
  • 提交

answer

#include<bits/stdc++.h>
#define re register
using namespace std;
inline int read(){
	re int t=0;re char v=getchar();
	while(v<'0')v=getchar();
	while(v>='0')t=(t<<3)+(t<<1)+v-48,v=getchar();
	return t;
}
const int M=998244353;
inline void add(re int &x,re int y){(x+=y)>=M?x-=M:x;}
inline int Mod(re int x){return x>=M?x-M:x;}
inline int ksm(re int x,re int y){
	re int s=1;
	while(y){
		if(y&1)s=1ll*s*x%M;
		x=1ll*x*x%M,y>>=1;
	}
	return s;
}
int n,m,fa[6002],ih[6002],val[6002],ans,deg[6002];
char s[3002][3002];
inline int root(re int x){return x==fa[x]?x:fa[x]=root(fa[x]);}
inline void Merge(re int x,re int y){
	++deg[x],++deg[y],x=root(x),y=root(y);
	if(x==y){ih[x]=1;return;}
	fa[x]=y,ih[y]|=ih[x];
}
int main(){
	n=read(),m=read(),read(),read();
	for(re int i=1;i<=n;++i)scanf("%s",s[i]+1);
	for(re int i=1;i<=n+m;++i)fa[i]=i;
	for(re int i=1;i<=n;++i)
		for(re int j=1;j<=m;++j)
			if(s[i][j]=='b')
				Merge(i,j+n);
	for(re int i=1;i<=n;++i)
		for(re int j=1;j<=m;++j)
			if(s[i][j]=='k'){
				++val[root(i)];
				if(root(j+n)!=root(i))++val[root(j+n)];
			}
	for(re int i=1;i<=n+m;++i)if(ih[i])ans=max(ans,val[i]);
	for(re int i=1;i<=n;++i)
		if(deg[i]==1){
			re int vv=val[root(i)];
			for(re int j=1;j<=m;++j)if(s[i][j]=='k'&&root(j+n)!=root(i))--vv;
			ans=max(ans,vv); 
		}
	for(re int j=1;j<=m;++j)
		if(deg[j+n]==1){
			re int vv=val[root(j+n)];
			for(re int i=1;i<=n;++i)if(s[i][j]=='k'&&root(j+n)!=root(i))--vv;
			ans=max(ans,vv);
		}
	printf("%d",ans);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3488kb

input:

7 3 4 5
bbb
..b
..b
k..
k..
k..
k..

output:

4

result:

ok "4"

Test #2:

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

input:

3 3 4 2
k..
kk.
bbk

output:

3

result:

ok "3"

Test #3:

score: 0
Accepted
time: 48ms
memory: 12616kb

input:

3000 3000 0 9000000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

0

result:

ok "0"

Test #4:

score: 0
Accepted
time: 167ms
memory: 12620kb

input:

3000 3000 8994001 5999
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

8994001

result:

ok "8994001"

Test #5:

score: 0
Accepted
time: 40ms
memory: 12524kb

input:

3000 3000 9000000 0
kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk...

output:

0

result:

ok "0"

Test #6:

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

input:

3000 3000 8997000 3000
bkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk...

output:

2999

result:

ok "2999"

Test #7:

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

input:

3 3 6 3
bkk
kbk
kkb

output:

2

result:

ok "2"

Test #8:

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

input:

1 1 0 0
.

output:

0

result:

ok "0"

Test #9:

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

input:

1 1 1 0
k

output:

0

result:

ok "0"

Test #10:

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

input:

1 1 0 1
b

output:

0

result:

ok "0"

Test #11:

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

input:

12 9 0 16
.........
.bbb....b
...b.....
.bb...b..
.b....b.b
.........
.........
..bbb....
.........
...bb....
.........
.........

output:

0

result:

ok "0"

Test #12:

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

input:

14 11 0 12
...........
.b.b..b..b.
...........
...........
...........
...........
...........
...........
.b.b..b..b.
...........
.b.b..b..b.
...........
...........
...........

output:

0

result:

ok "0"

Test #13:

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

input:

8 9 0 32
bbbbb.b..
..bbb.bb.
....bbbb.
bb...bbb.
.........
..bbbbbb.
.........
.bbbbb.b.

output:

0

result:

ok "0"

Test #14:

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

input:

10 7 0 12
b......
bbbb...
.b.....
...b...
...bb..
...b.bb
.......
.......
.......
.......

output:

0

result:

ok "0"

Test #15:

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

input:

41 36 82 172
....bk.......k.bb............b.....k
.....b...b..................b.......
.....b......k..b.........bk......k..
.bb...kb.....b.b....b.....b......k..
....k....bb.b.............bb....b...
........k.b.............b...bb......
.b..............b.b...............b.
b......b...b..bk...........k...

output:

82

result:

ok "82"

Test #16:

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

input:

29 42 25 22
...............b..........................
................................k.........
.....b....................................
.......b..................................
......k..........k...b....................
................k.........................
.........k..................k....

output:

6

result:

ok "6"

Test #17:

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

input:

41 36 82 540
....bkb......k.bb..bbb.b..b..b.bb..k
b...bbbb.b......bbb..bb.b...b..b....
b..b.b..b.bbkb.b....b.bb.bk......k..
bbb...kb..bbbbbb.b..bb.b.bb.....bkb.
..b.kbb..bb.b..b..bb......bbbb..bbb.
...b.b..k.b.......b..b..b...bb......
.b.....bb....bb.b.b.....b..bb.bb..b.
b..b...bb.bb..bk.....b.b...k...

output:

82

result:

ok "82"

Test #18:

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

input:

29 42 25 326
.b.............bb.b..b.b.b.b.b.b..bb.bbbbb
.b.....b........b........b......k.........
b....b..b...b.b...b......bb.b.bb...b.b....
.b..b..bbb...b.b.......b.b.b......b.b.b...
.b.b.bk..b......bkbb.b........b.....bb.bbb
..b..b....b.....k...........b.............
..b.....bkb..b.b.......b....k...

output:

25

result:

ok "25"

Test #19:

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

input:

55 58 327 1168
b......b....b.bb.b.bb.kbbb..b.b....kb...bbb..b..b.bkb..b.b
.b......b....b.bb..b.b.bb.bbb.bbbb.kbbb..bbb.k.....b.bb.b.
..bbkbkb.bkkb..bbkbk....b...b..b....bb..b...k..b.b...kb.b.
.k...bbbb......bbkbb.bb.bbkbb.k.b.k......bbb..b.b..kbbbbb.
bb.bb.....b.bb....k.kbbkb..b.b...b.bkb.b.b..bk.bk...

output:

327

result:

ok "327"

Test #20:

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

input:

41 36 266 724
..bbkkb.b...bk.kkb.bbb.b..b..k.bb.bk
k...bkbb.kbbbb.bbbb..bbbbb..kb.bb..b
bbbkbkbbb.bbkbbk.b.bbbbb.kk..b...kb.
bkkb.bkkbbbbbkbk.b.bkbbbbbkb..bbbkb.
..b.kbb..kkbkb.b..bb...bb.kkbb..kbb.
.b.b.bb.k.k.bb.b.bb.bbbbk.b.kk.b..bb
.k.bbb.bbb...bb.kbkbb.bbbbbbb.bb.bkb
k.bbb..kb.bkbbkkbb.b.bbbb.b...

output:

266

result:

ok "266"

Test #21:

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

input:

29 42 177 478
.b.b.bbbbbb....kb.b.bk.k.bbbbb.b..bk.bbbbk
.b.....b...b...bb....b.b.b......kb.bb.b..b
k....k.bk...k.kbbbb.b...bbb.k.bk...k.b....
bkb.kbbkkk...k.k.b...bbb.kbb.....bbbkbkbb.
bk.bbbk..b..b...bkbb.k.bb..b..k.....bb.bbk
..bb.kbb..k.bbbbk.bb.b..b.b.b...b.b..bb.bb
..b..bb.bkbb.b.k.b....bbbbbb...

output:

177

result:

ok "177"

Test #22:

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

input:

55 58 725 1566
k..bbbbb.b..k.bbbbbbbbkbbbbbbbb...bkk.bbbbk..k.bb.bkk..bbb
bb.....bb...bbbkkbbbbb.bbbkbkbbkkb.kkbb..bbk.k.bb.bkbkb.bb
bbbkkbkbbkkkb..bbkkk..b.kb.bb.bk.b..bkb.b..bkbbk.b..bkkbb.
.k.b.kbkb.bbb.bbbkbb.kbbbbkbkbkbk.kb.bbbbbkk..k.b..kbbkbb.
bb.bb..b.bbbkkb.b.kbkkbkkb.bbb.bbb.bkk.k.k..bk.bk...

output:

725

result:

ok "725"

Test #23:

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

input:

41 36 450 540
..bbkkk.b...bk.kkb.kkk.k..k..k.bb.bk
k...bkkb.kbbbb.bkkb..bbbkb..kb.kb..b
bbbkbkbbk.bbkkbk.b.bbbbk.kk..b...kb.
bkkb.bkkbbbbbkkk.b.bkkbbbkkb..bbkkb.
..b.kbk..kkbkb.k..bk...bb.kkkk..kkk.
.b.k.bb.k.k.bb.b.bk.bkbbk.b.kk.b..bb
.k.bbb.bbb...kb.kbkbb.bbbbbkk.kb.bkb
k.bbb..kb.kkbbkkbb.b.bbkb.b...

output:

450

result:

ok "450"

Test #24:

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

input:

29 42 329 326
.k.b.bbbbbb....kk.b.bk.k.bbkbk.k..kk.kkkkk
.k.....k...b...bk....b.b.k......kb.bb.b..b
k....k.bk...k.kbbbk.b...bbk.k.bk...k.k....
bkb.kbbkkk...k.k.b...bbb.kbk.....bkbkbkbb.
bk.bbkk..k..b...kkkk.k.bb..b..k.....kk.kkk
..kb.kbb..k.bbbbk.bb.b..b.b.k...b.b..bb.bb
..k..bb.kkkb.b.k.b....bkbbbb...

output:

329

result:

ok "329"

Test #25:

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

input:

55 58 1123 1168
k..bbbbb.b..k.kbbkbkkbkkkkbbbbk...bkk.bbkbk..k.bb.kkk..bbk
bk.....bb...bbbkkbbbbb.kkbkbkbbkkb.kkkk..kbk.k.bb.bkbkb.kb
bbkkkbkbbkkkb..bbkkk..b.kb.bb.bk.b..kkb.b..bkbbk.b..bkkbb.
.k.b.kkkk.bbb.bbkkkb.kkbkbkbkbkbk.kb.bbbbbkk..k.k..kbkkbk.
kk.kb..b.bbbkkb.b.kbkkbkkb.kbk.bbk.kkk.k.k..bk.b...

output:

1123

result:

ok "1123"

Test #26:

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

input:

41 36 634 172
....kkk.b...bk.kk..kkk.k..k..k.kk..k
k...kkkk.k.bbb..kkk..kkbkb..k..k...b
k..kbk.bk.kkkkbk...kkbkk.kk..k...kb.
kkk...kkbbkkkkkk.k..kkbk.kkb..bbkkk.
..k.kkk..kk.k..k..kk...b..kkkk..kkk.
...k.kb.k.k..b....k..kb.k.b.kk.b...b
.k..bb.kk....kk.k.kbb.b.kb.kk.kk..kb
k.bkb..kk.kkb.kkb..b.kbkb.b...

output:

634

result:

ok "634"

Test #27:

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

input:

29 42 481 22
.k......kkk....kk.k..k.k.kkk.k.k..kk.kkkkk
.k.....k.......kk....b...k......kk.kk....b
k....k..k...k.k.kkk......kk.k.kk...k.k....
kk..kk.kkk...k.k.k...bkk.k.k......kkk.kbb.
.k.kkkk..k..k...kkkk.k........k.....kk.kkk
..kk.k....k..k..k..b.k....k.k...k....k....
..k..k..kkkk.k.k......kk..k.k...

output:

100

result:

ok "100"

Test #28:

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

input:

55 58 1521 372
k....b.k.b..k.kkbk.kk.kkkk.bkbk...bkk.b.kkk..k.bk.kkk..kkk
.k......k....k.kkb.kbk.kkbkkkbkkkk.kkkk..kkk.k.bb..k.kk.kb
..kkkkkk.kkkk..kkkkk..k.k...k..k....kkb.k..bkb.k.k..bkkbk.
.k...kkkk.bb..bkkkkk.kkbkkkkk.kbk.k..b.bbkkk..k.k..kkkkkk.
kk.kk..b..k.kkb.b.k.kkkkkk.k.k.kbk.kkk.k.k..kk.kk...

output:

1521

result:

ok "1521"

Test #29:

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

input:

211 543 25246 8204
k....kk...k.............k.k......bkkb...kkb.....k.k....kkkbk.b........k.k..k..k.........k.kkkb..k.b..kkk.b..k..k........bkk...bkk...b.k..kk....bkk.k.k.kb.k........k....k..bk..b...b.kk.k...b...kk..kk...k.b..k..k...k.b.......k.....kk.kk.bk......k........k..k..kb...b.........k...k..b...

output:

25246

result:

ok "25246"

Test #30:

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

input:

322 134 9311 3231
.k.b.....k......k....kk....kk...b.k...kk.k....kk..k................bk..kk.kbk...k.....kb.bkk.kb..b....k.k.k..k...........k.kk.....kk..
..kbb....k..kkbbb.....kk.......b.k...kb.....b....kk.bb....kb...b.k.b......kb.....k..k....kb..b.........b....bb..k........b.b.k.kkk..bk
.k.b...........

output:

9311

result:

ok "9311"

Test #31:

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

input:

520 599 42212 6620
k...k......k.......k.........k......................k..b..........b.......................kk.....b..kk...........k.........kk.........k.....k....................b...b.kk.............k..k....k....k....kk.k........k.....k.....k..k...k..................k...k....b............k...........

output:

42212

result:

ok "42212"

Test #32:

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

input:

211 543 39567 22525
kbb..kk...kk.bb..bb.....kkkbb...bkkkk..bkkk..b..k.kk.bbkkkkk.k..bb....kbkb.k.bkb.b.bb.kbk.kkkk..kbk..kkk.k..k..kb..bbk..kkk..kkkk..kk.kb.kkb...kkkbk.k.kk.k.kb.bk.kk..k.kbbkk..k.b.k.kk.k.b.k...kk..kkb..kbk..kb.k...k.k.b.bb.bk.bb.kkk.kkbkkbbbb..k.b.k.bb.k..k..kk..bkb..bbb...k.bbk.....

output:

39567

result:

ok "39567"

Test #33:

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

input:

322 134 14704 8624
.k.k.....kbb..b.k.b.bkk..bkkk...k.kb..kkbk..bbkkbbkb..k.bb.bb.....kkk.bkkbkkk...k.b.b.kk.kkk.kk.bkb.k.kbk.k.bk..kkb.....bk.kk.....kkb.
b.kkkb...kb.kkkkk....bkkb......kbk..bkk.b..bk.k..kk.kk....kk.k.k.k.k......kk.b...kb.k..k.kkb.kkbb..bb..k.b..kk..k..b.b...k.kkk.kkk.bkk
.k.k.....bb...

output:

14704

result:

ok "14704"

Test #34:

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

input:

520 599 81147 45555
kb..k.bbkk.k..kk...k..kb..k.kkbk......b..b..k....b..kk.k.......b..kk.k...k...b.bbb........kkbkb..k..kk.....k.bbb.k..k..b...kk..bb....bk....bk...k.k.b.b..k.......k...k.kk.....k.k.....kk.k..b.k...bkb.bkkk.k.b..kk..kbb...k..k..k..k...kbb.k.b...b..b..bkbk..kkk.bkkk..kb..kb...k...b......

output:

81147

result:

ok "81147"

Test #35:

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

input:

211 543 53888 36846
kbk.bkk.bbkk.kkbbkb.b.bbkkkbkb.bkkkkkb.kkkk..b.bk.kk.kkkkkkkbk..bkbbb.kbkb.kbkkk.kbbkbkkk.kkkk.bkkkb.kkk.k..k..kkbbbbk..kkkbbkkkkbbkk.kbbkkkb..kkkkk.kbkkbkbkkbkk.kk.bk.kbbkk.bk.k.kbkk.kbbbkb..kkbbkkbbbkkkb.kkbkbb.kbkbk.bk.kkbbkbkkkbkkbkkkkkbb.kbb.k.bk.k..kbbkk.bkkb.bkkkb.bkbkkkbb...

output:

53888

result:

ok "53888"

Test #36:

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

input:

322 134 20097 14017
bkbkb..bbkbk.bbbk.bbkkkb.kkkk.bbkbkk..kkkk..bbkkkkkkbbkbbb.kk...bbkkk.bkkkkkkb..k.bbk.kkbkkkbkkbkkkbk.kbk.kbkkbbkkbbbb..kkbkkb....kkk.
k.kkkbbbbkkbkkkkk.bbbbkkb.bb...kbkbbkkkbkb.kk.k.bkkbkk.b.bkkbk.kbkbkbb.bbbkk.bbbbkk.kbbk.kkb.kkkk.bbkb.kbkbbkkbbk.bkbkbb.k.kkkbkkkbbkk
bkbkbb...b...

output:

20097

result:

ok "20097"

Test #37:

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

input:

520 599 120082 84490
kkbbk.kbkk.kb.kk.b.k.bkk..k.kkbkb.....k.bkbbkb...k..kkbk.bb...bkbbkkbk..bkb..kbkbb..bb.b.bkkkkk..kb.kk..bb.kbkbk.kb.k.bbbbbkkb.kbb...kk.bb.kk.bbk.k.kbk..kbb..b..k..bkbkk.b.b.kbk..b.bkkbk..k.kb.bkkk.bkkk.kbkb.kk.bkkkbbbk..k.bk..k.b.kkkbk.k.b.k..kb.kkkkb.kkk.kkkk..kkb.kkbb.kb.bk.....

output:

120082

result:

ok "120082"

Test #38:

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

input:

211 543 10925 22525
b....kb...k.............b.b......bbkb...kbb.....b.b....bbbbk.b........b.k..k..b.........b.bkbb..b.b..kbk.b..k..b........bkk...bbk...b.b..bb....bkb.b.b.bb.b........k....b..bk..b...b.kk.b...b...bk..bb...k.b..b..k...k.b.......b.....bk.bb.bb......k........b..b..bb...b.........b...b.....

output:

10925

result:

ok "10925"

Test #39:

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

input:

322 134 3918 8624
.b.b.....k......b....bb....kb...b.b...kb.b....bk..b................bb..bk.kbk...b.....bb.bbk.kb..b....b.k.b..k...........b.bk.....kb..
..bbb....k..bbbbb.....kb.......b.k...kb.....b....bk.bb....bb...b.k.b......bb.....b..k....bb..b.........b....bb..k........b.b.k.bbb..bk
.k.b...........

output:

3918

result:

ok "3918"

Test #40:

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

input:

520 599 3277 45555
k...b......b.......b.........b......................k..b..........b.......................bb.....b..bb...........b.........bb.........b.....b....................b...b.bb.............b..b....b....b....bb.b........b.....b.....b..b...b..................b...b....b............k...........

output:

3277

result:

ok "3277"

Test #41:

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

input:

211 543 25246 36846
kbb..kk...kb.bb..bb.....kbkbb...bbkkb..bkkb..b..k.kb.bbkkkbk.b..bb....kbkb.k.bkb.b.bb.bbk.kkkb..kbb..kkk.b..k..kb..bbb..bkk..bbkk..bb.kb.kkb...bkkbk.k.kb.k.bb.bb.bk..b.kbbbk..b.b.b.kk.k.b.b...kk..kkb..kbb..kb.k...k.b.b.bb.bk.bb.bkk.kkbbkbbbb..k.b.b.bb.k..k..kb..bbb..bbb...k.bbk.....

output:

25246

result:

ok "25246"

Test #42:

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

input:

322 134 9311 14017
.k.b.....kbb..b.k.b.bkk..bbkk...b.kb..kkbk..bbkkbbkb..b.bb.bb.....bbk.bkkbkbk...k.b.b.kb.bkk.kb.bbb.b.kbk.k.bk..bbb.....bk.kk.....kkb.
b.kbbb...kb.kkbbb....bkkb......bbk..bkb.b..bb.b..kk.bb....kb.b.b.k.b......kb.b...kb.k..b.kbb.bbbb..bb..b.b..bb..k..b.b...b.bbk.kkk.bbk
.k.b.....bb...

output:

9311

result:

ok "9311"

Test #43:

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

input:

520 599 42212 84490
kb..k.bbbb.k..bb...k..bb..b.bkbb......b..b..b....b..kb.b.......b..bb.b...b...b.bbb........kkbbb..b..kk.....b.bbb.k..b..b...kk..bb....bk....bk...b.b.b.b..b.......b...b.kk.....b.b.....kb.k..b.k...bkb.bbkk.k.b..bb..kbb...k..b..k..k...kbb.b.b...b..b..bbbk..bkb.bbbb..bb..bb...k...b......

output:

42212

result:

ok "42212"

Test #44:

score: 0
Accepted
time: 70ms
memory: 11952kb

input:

2848 2717 254666 3074724
.b....k...bb.b...b..b.b...k..b..b.....bb....bb.b.b.......bb..b.bbbb..bbb..b..bb..bb.b....bb.b....b..b...bb....b..bk...bbbb.b..kb..b.b.b..b...bbbb..b..bb.bb....bbb...bkb.b...b.b.b.b.b.b.bb..bb....b.b.....bb.b......b.k.k.b.kbb..bbkbb.b..bb.b..bbb.bb.bk..bbbb..bbbk.bbb....b.b.....

output:

254666

result:

ok "254666"

Test #45:

score: 0
Accepted
time: 63ms
memory: 11472kb

input:

2635 1922 616530 2339859
.bk.b....k....bb.kbb...bk...b..bb.bk..bbk..b.b....b...bbbb.bbbb.k...k....kkb..b.bb...b.b...bkbbbbb....b..b..bbb.bb..b..k..b.kkb..b.b.b.b..bbk.b.b...b..bkb.k....b.b.b..b.b.k...bkbb....bbbbbkb.b.k.bb.kbbk..kk..bb..b..bbkbb.bbk..b.k...bbbkbb.b.kbbb.bb....bb.bb.b..b.bbb.k...bbkk...

output:

616530

result:

ok "616530"

Test #46:

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

input:

1344 1719 129596 979662
...b.b....bbbbb.bb.b..bb.b.b.b.....bb...b.kbb.bb..bbkb..k....bk..kbk.bb...b...b..bbbbb.b..b.bbbbb..bbbbbb....b..bb...k.....bb..bk....bkkbb.bbk..k........bk.b.b..bb.b.bb.k...k..kb.bk..b...b.bb.b...b.k.b..bbb.....b...b..bbb.b....bbkb.bb....b..b.b.bbbbbbbbkbb.b....b...bbbk..b..k...

output:

129596

result:

ok "129596"

Test #47:

score: 0
Accepted
time: 54ms
memory: 12008kb

input:

2848 2717 2189170 172968
......k.............k.k...k............k....bk.k.k........k..k..k.k..kkb..k..k...kk.k....k.......b..k....k....k...k...kkkk.k..k...k.k........kkk......k..kk....k......k..k.....k...k.k.......k.......k.....k..k......k.k.k.k.kkk..kkkkk.k..kk.k..bkb.bk.kk..kkkk...k.k..kk....k.k.....

output:

2189170

result:

ok "2189170"

Test #48:

score: 0
Accepted
time: 54ms
memory: 11416kb

input:

2635 1922 1882646 440685
.kk......k....bk.kbk....k...k...k..k..kbk..b......k...kk.k..k.b.k...k....kk...k........k...kkb.bk.....k..b....k..k..k..k....kkb....b.k......k...k......kk..k......k.k....b.k....kkk....bkkb.kb...k.bk.k.kk..kk...k.....kkk...kkk..k.k...bkkkkk.k.kk.k.kb.....b.b..k.....k..k...k.kk...

output:

1882646

result:

ok "1882646"

Test #49:

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

input:

1344 1719 707180 113286
...k.k....k.kbk.kk.k..kk.b.k.k.....kk...k.k...kk...kkb..k....kk..kkk.k....k..........k.k....kkb.k...bkk.k....k..bk...k.....kk..kk.....kkk..kbk..k.........k.k.k..kk.k.kk.k...k..k..kk..b...k.kk.k...k.k.k....k.....b......kkk.......kk..kk....k..b.k..bkkkk.kkk...........k.kk..k..k...

output:

707180

result:

ok "707180"

Test #50:

score: 0
Accepted
time: 103ms
memory: 12048kb

input:

2848 2717 3156422 3074724
bkb.b.kbbbbkbkbbbbb.kbkbbbkb.b.bkbb..bkkbb.bkkbk.kb.bbb.bkkbbkbbkkk.bkkk.bkbbkk..kkbk...bkbbkb.b.k.bkb..kk.b..k.bkkb.bkkkkbkbbkkbbkbkbk.bb..bkkkkbbk..kkbkk.bbbkkbbbbkkbbkb..k.kbkbkbkbbbkbbbkk.b..b.k.bb.bkb.kbbb.b.kbkbkbkbkkk.bkkkkkbkbbkk.kbbkkkbkk.kk.bkkkk.bkkkkbkkkbbbbkbk....

output:

3156422

result:

ok "3156422"

Test #51:

score: 0
Accepted
time: 78ms
memory: 11248kb

input:

2635 1922 2515704 2339859
bkkbkbbbbkbb.bkkbkkkbbbbkbbbkbbbkbbkbbkkkbbkbkbbb.kbbbkkbkbbkbkbkbbbkbbbbkkk.bkbbbbbbbbkbbbkkkkkkbbbbbkbbk..bkkbkkbbkbbkbbbbkkkbbbbkbkbkb.bkkbk.kb.bkbbkkbbkbbbbkbkbkbbbbkbkb.bbkkkb.bbkkkkkkkbkbkbkkbkbkk.bkk..bkbbbbbkkkbbbkkkbbkbkbbbkkkkkkbkbkkbk.kkbbbbkkbkbbkbbbbkkbbkbbbkkk...

output:

2515704

result:

ok "2515704"

Test #52:

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

input:

1344 1719 995972 979662
b.bkbk.bbbkkkkkbkk.k.bkkbkbkbkbb.bbkk..bk.kkbbkk.bbkkk.bkbbbbkkbbkkkbkbbb.kbbbkbbbbkbk.k.bbbkkkkkbbkkkkbkb.b.k.bkkbbbkb.bbbkkbbkkbbbbkkkkk.kkkb.kbbbbbbbbbk.k.kbbkkbkbkkbkbbbk.bkbbkkbbkb..k.kkbk..bk.kbk.bkkkbbb.bk.bbkb.kkk.kbbbbbkkb.kkb..bkb.kbk.kkkkkkkkkkk.k.b.bbbbbkkkkbbk.bk...

output:

995972

result:

ok "995972"

Test #53:

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

input:

2848 2717 3156422 1140220
.k....k..bbk.kb.bb..kbk...kb.b.bk....bkk....kkbk.k..b.b.bkkbbkbbkkk..kkk.bk..kk..kk.k....kbbk....k..kb..kk....k..kkb.bkkkk.kb.kk..k.k.k..b...kkkkb.k..kk.kk.b.bkkb..bkkb.k...k.kbk.kbk.bbkbb.kk....b.k....bkb.kb.....k.k.k.k.kkk..kkkkk.k.bkk.k.bkkkbkk.kk.bkkkk..kkkkbkkk....k.k....

output:

3156422

result:

ok "3156422"

Test #54:

score: 0
Accepted
time: 67ms
memory: 11408kb

input:

2635 1922 2515704 1073743
.kkbk...bkbb.bkk.kkk...bk.b.k..bkbbkbbkkk.bk.k..b.kb.bkkbk.bkbk.k...k..bbkkk..k.bb.b.b.k...kkkkkkb.b.bkb.k..bkk.kkb.kb.k..b.kkk..b.k.kbk..bkkbk.k..bk..kkb.kb...k.kbk.bb.kbk..bbkkk....kkkkkkk.kbk.kkbkbkk..kk..bk..bbbkkkbb.kkk..kbk..bkkkkkk.k.kkbk.kk.bb.kkbkb.k..b.kkb.k...kkk...

output:

2515704

result:

ok "2515704"

Test #55:

score: 0
Accepted
time: 38ms
memory: 7612kb

input:

1344 1719 995972 402078
..bkbk....kkkkkbkk.k.bkk.k.k.kb..b.kk...k.kkb.kk.bbkkk..k...bkkb.kkk.kbb..kb..k..bbkbk.k..b.kkkkk..kkkkbkb.b.k..kk...k..bb.kkb.kk.b..kkkkk.kkk..k.bb.b.b.bk.k.kb.kk.k.kkbkbb.k..kb.kkb.kb..k.kkbk...k.k.k..kkk.....k...kb.kkk.k....bkkb.kk...bk..k.k.kkkkkkkkkkk.k...bb...kkkk..k.bk...

output:

995972

result:

ok "995972"

Test #56:

score: 0
Accepted
time: 95ms
memory: 12152kb

input:

2848 2717 2189170 3074724
bbb.b.k..bbbbbbbbbb.kbkb..kb.b.bb....bbk.b..bkbk.kb.bbb.bbkbbkbbkbk.bkkb.bk.bkb..kkbk...bkbbb..b.b.bkb..bk.b..k.bbkb.bkkkkbkbbkbb.k.k.b..b...kkkbb.b..kbbkk.bbbkbbbbbbkb.kb..b.kbb.kbkbbbbbbbkb.b..b.k.bb.bkb.kb.b...kbk.k.k.kkk..kkkkk.kbbkk.k.bbkbbbk.kk.bkkkk..bkbkbbkk.bbbk.k....

output:

2189170

result:

ok "2189170"

Test #57:

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

input:

2635 1922 1882646 2339859
bkkbb..bbkbb.bbk.kbkb..bkbb.kb.bkbbkbbkbk.bb.b..b.kb.bkkbk.bkbbbkb.bkbbbbkkb..kbbbbbbb.kbbbkkbbbkb.bbbkbbb..bbkbbkbbkbbk.bbbkkb..b.b.kbbb.bbkbb.kb.bb.bkkb.kb.b.b.kbk.bbbbbk..bbkkk...bbkkbbkb.bbkbbkbkbkk.bkk..bkbbbbbkkkbb.kkkbbkbk.bbbkkkkkbk.kkbk.kbbbb.bbbbb.k..bbbkbbk..bkbk...

output:

1882646

result:

ok "1882646"

Test #58:

score: 0
Accepted
time: 31ms
memory: 7624kb

input:

1344 1719 707180 979662
b.bkbk.bbbkbkbkbkk.k.bkk.bbkbkbb.b.kk...k.kbb.kk.bbkkb..kb..bkkbbkkk.kbb..kb.bbb.bbbbk.k.bbbkkbbkbbbbkkbkb.b.k..bk..bk..bbbkkb.kkbbb.bkkkb.kbkb.kbbb.b.b.bk.k.kb.kkbk.kkbkbbbk..kbbkkbbbb..k.kkbk...k.k.k..bbk.b..bb...bb.kkk.bbb.bbkkb.kk...bk..b.k.bbkkkkbkkkb.b...bbbbbkbkk..k.bk...

output:

707180

result:

ok "707180"

Test #59:

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

input:

2993 2996 2177966 2106796
b..bbk.kbbb.kkkbbb.k....kbkk....bkkbk.........b.b..kk.kkbk..bb.bb.bbkk.k.kbk.b.b..k..bk..k.b.kk..b.k..b.k..kb.b.k...k....b.kk.b.....b...bkkk.b.kbb.b....kk.bk..k.k.b.b..b..k.bbbb.b..kk.b.bb.k.k...k.bkb.b.kk..kkbbbk..k.k....k.bkkkk.b...b....b.k..b.bkb...k.k..k.k..bbk.b.kb.......

output:

2177966

result:

ok "2177966"

Test #60:

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

input:

2993 2991 1661051 1971187
b.k.k.b.k...bb.k.b.....k..k..k...b.k.kb....b.b...k..k...k.b......b..bkkbb....b...b.k..bb.k..b.b......bb.k...b.k.....b.kbkb.b..bk..kbk.bk...kb....k.b.b.....k.b...b....k...bbb..bbkk.bk.b......k..kk.b.....b.b..b.bkk..b.bb.....b..bk..bb.b..k..bk.....b.kk.bbk...b.k..k...b.bk..b....

output:

1661051

result:

ok "1661051"

Test #61:

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

input:

3000 2994 1971760 1205231
...b.b.b.......k.bb.b..kb.kb..kkkbk.kk..bbkb.b.b.....k.k..kk.bb.........kk....k...k..k....k..b..k.....bb.k.b.b.........k....k..k.b....kb.......kb.k...kbk..kb.....b.bb..bkkkkk..k.....kk.k.............k....b....bbk...k.b...k..k.b.k.bb......k.....kb..k.b.b.bkk.....kk..kbk..k.....

output:

1971760

result:

ok "1971760"

Test #62:

score: 0
Accepted
time: 95ms
memory: 12356kb

input:

3000 3000 4494770 4000
bb......................................................................................................................................................................................................................................................................................

output:

3995984

result:

ok "3995984"

Test #63:

score: 0
Accepted
time: 86ms
memory: 12584kb

input:

3000 3000 4494092 4000
bb......................................................................................................................................................................................................................................................................................

output:

3994647

result:

ok "3994647"

Test #64:

score: 0
Accepted
time: 104ms
memory: 12580kb

input:

3000 3000 4496428 4000
bb......................................................................................................................................................................................................................................................................................

output:

3996867

result:

ok "3996867"

Test #65:

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

input:

163 210 4247 307
..............................k........k........b.....k....k..k...k....k........k.........k.........k..k.............k....................k......k...k....k............kk............................k...k...k....
...................k............k..k......b....k...kk......................

output:

2448

result:

ok "2448"

Test #66:

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

input:

97 51 844 111
.........k.bk.k...........bk............k..b..b..kk
....................kkk..........k......k..k.......
........k....k..kk..k....b...k..k..k........kk..k..
..k.k..k......k......k.k....k..........kk.......k..
kk.....k........k...k......k...kk...k..k.k.........
..kb....k..k.b.....b.....k...

output:

844

result:

ok "844"

Test #67:

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

input:

71 153 2540 130
.k........k.................k....k................k.k....kk..k......kk........k.b.kkkk.k..kk........k...k.........kk.kkk.k.......k......k...k.......k...k
.k...k.....k...k...k........k.........k......k.k..k...kk...k..kkk.k......k........kk.kk...k..k.kk......k..........kk....k.k....kk....

output:

1579

result:

ok "1579"

Test #68:

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

input:

163 210 27274 310
kkkkkkkkkkkk.kkkkkkkk...kkkkkkkkkkkkkkkkkk.k.kkkkkkkkkk.kkk.kkkkkkkkk.kk.kk..kkkk.k...kkkkkkk.kk.kkkkkk.kkkkkkkkkkkkkkkkkkk..kkkkkkkk.kkbkkkkkk.kkk.k.k..kkkkk.kkkkkkkkk.kkkkkkkkkkkkkkkkkkkkkkkk..kk.kk..k.k.kkkk
k.kk..kkkkkkkk.kkkkkkk.kkkkkkkkkkkkkkkkkkkkkkk.kkkkkkkk.kkkkkkk.kkkkkkk...

output:

15737

result:

ok "15737"

Test #69:

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

input:

97 51 4003 119
kkkkkkkk.kk.k.kkk.kkkk.kbkkkkkkkkkk.kkkkkkkkk..kkkk
kkkkkkkkkkkkkkkkk.kkkkkkkkkbkk.kkk.kkkkk..kk.kk.kkk
.kbkkkk.kkk.k.kk.kkkk.kkkkkkk.kkkk.kk.kkkkkkkkkkkk.
kkkkkkk.kkk.kkkk.b.kkkkkkkk.kkkk.kkkkk.kkk.kkkkkkkk
kkkkkkbkkkk..kkkk.kkkkkk.kkkk..kkkkkkkkkkkkkkkkkkkk
kk.kkkkkkkbkkkkk.kkkkkkkk...

output:

2386

result:

ok "2386"

Test #70:

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

input:

71 153 9332 133
kkkk.kkkk..kkk.kk.kk.kkkk.k.kkkkk.kkkkkkkkkkkkkk.kkkkkkkkkk.kkkkkkkkkkkkk.kk.k.kkkkk.kkkk.kkkkk..kkkbk.kkkkkkkkkkkk.kkkkkkkkkkkkkkkkkk.kkkkkkkkkkkk.kkkkk
kkk.kbkk...kk.k.kk.kk.kkkkkkkkkkkkkk.kkkkkkkkkkkkk.kkkkkkkk.kkkkkkkkkkkkkkkkkkkkkkkk.kkk.kk.k.kkk..kkkkkkkkk.kk.kkkkkkkkkkk.kkkkkk...

output:

5247

result:

ok "5247"

Test #71:

score: 0
Accepted
time: 98ms
memory: 10960kb

input:

2509 2930 1860802 5023
k......k.k..k.k..k...............kkk....k.....k........kk.......k.k.....kkk....k....k..kk...........kk.........kk.kk..................k..k....k...k..k.....k.....k..k...kk....k.......kkk....k..k.k...kk.k..........kkkk....k.k..............k..k..k....k...k...k.k.k...k.......k.k.....

output:

1634061

result:

ok "1634061"

Test #72:

score: 0
Accepted
time: 120ms
memory: 12164kb

input:

2894 2188 2976833 4378
k..kk........kk.k...k.kk..k...k........kk......k.kk...kk...kkk..k......k.kkk.kkk.k....kk.kkk..k....k.....k.....k.k.kkk.....k..kkkkk.kkk...kk.k..k...kkk...k...k.k..k.kkk.kkkk.kk........k.k.kkkkk...kk.......k.kkk.k..kk.k..kkk.k.....kk.kkkkkkkkkkk.k.kkkk..k.kk.k..k.k.k.k...kk.......

output:

2879945

result:

ok "2879945"

Test #73:

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

input:

2934 2884 4042533 5744
....k.k.k..k....k.kk....kkk.kkk.kkk.kkk.kkkkkk.k.kkk...k..kkkk...kkkkk.....kkkkk.kk.k.k.kk..k.kkkk..k...k.kk.kk...kk..k.k.kk.kk..kkkk.k.k......k....kkk..kk.kk.kk.kkkkkk..kkkk..k...k.kk.k..kkk.k.k..k.kk..kk.kkkk.kkkk..k.kkkk...k.kk.k.k.k..k.kkk.k.k.k..kkkk.kk..k.k...k.kkk.k...k...

output:

3950088

result:

ok "3950088"

Test #74:

score: 0
Accepted
time: 138ms
memory: 10900kb

input:

2509 2930 5496332 4780
k.kkkkkkkkkkkk.kkk.kkkkk...k.k.k.kkkkk.kk.k...kkkk.kk.kkkkkkkkkkkkkkkkk.kkkkk.k.kkkkkkkkkkkkkkkkkkkkkkkkkkkk..k.kkkkk.kkkkkkkkkkk..k.k.kkkkkkkkkkkkk.kk.kkkk.kkk.kk.kk..kkkkk.k.kkkkkkk.kk.kkkk..kk.k..kkk.kk.kkkkkkkk.kkk.k..kkkkkkkkkk.kk.kk.kk.k.kkkkk..kkkkkkk..kkkkkkk..kkkkk.kk...

output:

4263657

result:

ok "4263657"

Test #75:

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

input:

2894 2188 4109278 4168
kkkkkkk.kkk.k...kk..kkk..k....kkkkkk.....kkkk.kkkk....kkkkkkkkkkkkkk..kkkkkkk......kk.kkkkkkk.kkk.k.kkkk.k.kkk...k..k.kkkk.kkkkk.k.....kk...k.kk.kkk.k..kk.k.kkk..k..kk.kkkk..kkkkkkkkkkk.k.k.kkkkkkk.kkkkkkkkkk.k.kk.kk.kk.k.kkk.k.kkkk..kkkkkkkkkkk.kkkk.kkkk..kkkkkkkkkk...k..kk.....

output:

3948938

result:

ok "3948938"

Test #76:

score: 0
Accepted
time: 146ms
memory: 12152kb

input:

2934 2884 4777345 5558
kk.kkkk..kkk.....kkk.kk..kk.kk.kkk.k..kkk.kk..k.k..k..kk.....kkkkkkk.kkkk.k.k....kkk.kk.k.k..k..kk...kk..k...k.k..kkkkkkkk.k.kkk.kk..kk..kkk....kkk..k.k.kk.kk.kkk.kkkkkk.kkkk.k.k..kk.kkkk.kkk......kk....k..kkk..k.kkk.kkk.k.k....k.kkkk.kk.kkkk.kk.....k.kk..k..k...k..kk..k..kkkk...

output:

3471049

result:

ok "3471049"

Test #77:

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

input:

3000 3000 7048 5991
.............................................................................................................................................b.............................................................................................................................................

output:

3015

result:

ok "3015"

Test #78:

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

input:

3000 3000 3020 5997
...........................................................................................................................................................................................................................................................................................

output:

3017

result:

ok "3017"

Test #79:

score: 0
Accepted
time: 70ms
memory: 12384kb

input:

3000 3000 139470 5991
......................................................................................................................................................................................................................k..................................................................

output:

137547

result:

ok "137547"

Test #80:

score: 0
Accepted
time: 76ms
memory: 12452kb

input:

3000 3000 3005 5996
...........................................................................................................................................................................................................................................................................................

output:

2999

result:

ok "2999"

Test #81:

score: 0
Accepted
time: 129ms
memory: 12448kb

input:

3000 3000 4497400 5992
kkk.kkk.k..k.kkk.k..kkk.kk.kkkkk..k.k.kk.k....k...k..kkk...kk..k..k.kkk..k.k......k.k.k...k...kk.k.kkk..k.kkkkk......kkk..kkkkk.k..k.kk..k..k...k.kkkk..kkkkk...kkk..kk..kk.kk..k...kk..k..k...k.kkk.kkkkk..k.k..k..kk.kk.k.k.kk..k...kkk.kkk.kkk.kkk....k..k..k..kkk.kk...k.kk....k....

output:

4496023

result:

ok "4496023"

Test #82:

score: 0
Accepted
time: 152ms
memory: 12500kb

input:

3000 3000 5636181 5137
.kkkk.kkkkkkkkkk..kk.kkkk.k...kk.kkkkkkkkkkkk.kkkk.kkkkk.k.kk.kkk.kkkkkkkkk.k.kkkk.kkk.kkk.kk.kk...kkkkkkkkkkkkkk.kkkk.kkk.k.kkk.k.kkkkkkkk..kk.kkkkkkkk.kkkkkkk.kkkkk.kk.kkkk.kkk.kkkkkkk.kkkkkkkkkkk..kkkkkk.kkkkkkkkk..kk.kkk.k.kk..kkk.k..k.k.k..kkkkk.k.kkkkkkkk.k.kk.kkkkkkkkkk...

output:

20858

result:

ok "20858"

Test #83:

score: 0
Accepted
time: 205ms
memory: 12324kb

input:

3000 3000 5829119 4363
..kk....kkkk..kkk.k....k....kkk.....k.......kk.k..k..k.k...k.kk.......k.kkkk.kk.k.....kk.k......kkkk...k...k.k.kk............kk.k..k...k.k.kkkkk.....kkk.kk...k..k....kk.k.kk..k.k.k...kk.k..k.k..kkkkk.k..kk.kk.kk......kk.k..k.....k....kk....k.....kkkkk.kkkk.k..kkk.kkk..k...k......

output:

8869

result:

ok "8869"

Test #84:

score: 0
Accepted
time: 189ms
memory: 12472kb

input:

3000 3000 3659039 3606
kk.kkkk..kk.kk.kk.k.kk..kkkkk..kkk.k....k....kk..k.k.kkk...kkkk.k....kk.k..k......kkkkk.kk...kkk...k...kkkkkkk......k...kkk.kk..kk..k..kk.kk.k.k..k.k...kkkkk....k....kk...k...k..k...k...kkk.k.....kk.kk.kk....kkk.k.kk.k.k..kkkk..k.kkk..kkkk.kkkkk..k.kkk.k..kk.kkk..k...k.k.k..k....

output:

3052

result:

ok "3052"

Test #85:

score: 0
Accepted
time: 135ms
memory: 12320kb

input:

3000 3000 1641237 4832
k........k.........k.k.....k....k.....k..kkkk.........kkk.k........k...............k...........k...k.k....k........k............k..............kkk...k....k.......k......k...k....kk..k.....k..................k..........................kk.......k.k..........kkk...k...k.kk.k..k.....

output:

2970

result:

ok "2970"

Test #86:

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

input:

3000 3000 3905537 5258
.k...k...kkkk.k.kkk.k..k.k...k...kkkkkkk..k....k..k...kkk.k.......kk.kkk.k.k.k..k..k..........k.....kk..k.k.kkk..k..k.k.kkkk.kk......k.kkk...kkk.k.k.k.k.kkk..kkkk.....k.kkkk.k.k...kk.k...kk..kk.kk..k.kkkk.k.k..kk..k.....kkkk.kkkk...kkk.k.kkkk......kkkk.kkk...kkkkk.....k..k.......

output:

14846

result:

ok "14846"

Test #87:

score: 0
Accepted
time: 159ms
memory: 12384kb

input:

3000 3000 4497160 6005
kkkk..k...k....kk.kk.kk.kk...k.........k...kk.kk.kkk.kkk..kkkkkkkk..kk...........kk.k.kk.k.k.k..kkk.kkkkk....k.kk..kkkk..............k.kkkkkkk..k...kk.k.kkkk.kk.k.....kk.kk..k.k..kkkk..k.kkk...kk......k.kk..kkkk.k.kkkkk.kkkkk.kk.k.kk..k.k.k..kkk...k.kk.k....k.kkkkkk.kk.k.kkk.k...

output:

4495802

result:

ok "4495802"

Test #88:

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

input:

3000 3000 11318 5997
..........................................................................................................................................................................................................................................................................................

output:

7512

result:

ok "7512"

Test #89:

score: 0
Accepted
time: 59ms
memory: 12388kb

input:

3000 3000 3691 6005
...................................................................................................b...............................................................................b.......................................................................................................

output:

3002

result:

ok "3002"

Test #90:

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

input:

3000 3000 9392 5995
...........................................................................................................................................................................................................................................................................................

output:

6003

result:

ok "6003"

Test #91:

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

input:

3000 3000 20973 6003
.....................................................................................................................................................k....................................................................................................................................

output:

20943

result:

ok "20943"

Test #92:

score: 0
Accepted
time: 164ms
memory: 12460kb

input:

3000 3000 4496178 6000
..k...k.kk.....k..kk..k..kkk...kkk..k.kk.......kkkkkkkk..kk..k.kkkkkkkkkk.k..k.k....kkkk.k.....kk.k.....kk.k..k...k..kkkkk.kkkkk..kkk...kkk..k..kk.kk..k.....kkk.k.k..k.k..kk.k....k..kkk...kkk......kk......k.kk.kkk..kk.....kk...k.k.k.k.kk.kk..k.k...k...kkk..kk.k.k.k.......k...k...

output:

4496178

result:

ok "4496178"

Test #93:

score: 0
Accepted
time: 134ms
memory: 12384kb

input:

3000 3000 4497776 5995
.kkkk.kkk.k.kkkk..k.k.kk.k...k.k...k....k.k.kk....kkkk....k.kk.k.kk..kkkk.kkkkk.kk.....kk...k.kk...kk.kkkkk..k.kkk....k.kkk..kk..k....k..kk..kkkk.k.kk.k...kkk....kk...k...k..kkk.k..kk..kk.k..k..k..kkkkk.kkk....k...kk..kk..k.k..kk.k.k..k...k....k.k..k.kk...kkkkk....k.kk.kk..k.k...

output:

4497743

result:

ok "4497743"

Test #94:

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

input:

3000 3000 4458 6008
...........................................................................................................................................................................................................................................................................................

output:

3032

result:

ok "3032"

Test #95:

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

input:

3000 3000 3222 6002
...........................................................................................................................................................................................................................................................................................

output:

2944

result:

ok "2944"

Test #96:

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

input:

3000 3000 22479 5991
..........................................................................................................................................................................................................................................................................................

output:

14985

result:

ok "14985"

Test #97:

score: 0
Accepted
time: 182ms
memory: 12460kb

input:

3000 3000 6390668 4679
kkk..kkkkk.kk.k.k.kkkkk.kkkkk.k..kk.kkkk.kk.kkkkk.kkk.kk.kkkkkkkk.kk.kkkkkkkkkkk.kkkk.kk.k.kk...kkk...k.kk.kkkkk..kk...kkkk.k.kkk.k.k.kkk.k.....kkkk.kkk.kk.kkk..k.kkkkkkkkkkk.kkkkkk.kk.kkk.k..k.kkkk.k.kkkk.k.kk.kk..kk...kkkkkkkkkkkkkkk..kk....k.kkk.....k..k.kkk..kkk..kk.k.kkk....

output:

10528

result:

ok "10528"

Test #98:

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

input:

3000 3000 799044 6009
...........kk...k.....k.............k....k...kkk...kk...k.k....k......k.k............k............k.k.k..kk......k.k.k...k..kk...k.......kk..k.............k............k...........k...k..k...............k.....k.k.........k.....kk...k...........k..k..............kkkk.....k.....k...

output:

26984

result:

ok "26984"

Test #99:

score: 0
Accepted
time: 209ms
memory: 12388kb

input:

3000 3000 4364331 3068
kk.k..kkk.kkkkk..kk..k...k.k...kkkkkk....kk.k....kkk........kk.kkkk...kk.kk.k..k..kk.kk.kk..k..kk.k..k.kkk.....kk.kk..k.kk.kkkkkk.k.....k...kk.k.k.k.kkk.....kk.k.....kk.k.k..kk.k..k..kkk.k.k..kkkkk.kkk.....kk..kkk.....kk...kk.kk.k..k...k...kkk.k.kk..k.k.kk.k.kk.k..kkkk.k.kk.kk...

output:

2969

result:

ok "2969"

Test #100:

score: 0
Accepted
time: 103ms
memory: 12460kb

input:

3000 3000 2123187 5869
kkk...k.k.k.kk..kkkk.kk.kk.k.k..k..k......k.kk.k.......k..k......kk..kkkkk.kkk..k.kkk..k..k..kk.kk..k..kkk.k....kkkkk....k............kkk.kkkk..k.k...kk..k..kk.k...k..k.k....kk..k.k.kkk...k.....k.k...kkk..kkk..kk..k...k.kk...k..kkkk......kkk.kkkk..kk..k...k......k..k.kk.k........

output:

7452

result:

ok "7452"

Test #101:

score: 0
Accepted
time: 148ms
memory: 12328kb

input:

3000 3000 4030038 5199
.......k.......kk....k..........k.k......k..kk.k.k..kkk...kk..kkk..k.k.......kk.....kkk.........k.k......k..kk.....k.k...........k..k.....k........kkk.....kk.....k...k.k......k....k.......kk.....k.kk...k..k...kk........k.....k.k..kkk.....k.k.k.kk.k.....k...k...kk.......kk........

output:

7484

result:

ok "7484"

Test #102:

score: 0
Accepted
time: 201ms
memory: 12468kb

input:

3000 3000 4260128 4113
k.k...k...kk...k.k..k.k.kk...k..kk.k.kkkkk.kkk.k.k...k.k.k...k.k.kkkk.kk.k.k.kk.kkkkk.kkkkk.kk....kkkk..k..kkkkkk.k.kkk.kkk.kkk.....kk..k.k.....k.kk.kk..k.k...kk....k..kkkk.kkkk.kkk.k....k.kkk..k..k...kkkk.kk.k.kkk....kk.kk.kk...kkk.kk.kkkkk.kkk.k..k.kk.k.k..k....kkk......k.kk...

output:

4517

result:

ok "4517"

Test #103:

score: 0
Accepted
time: 144ms
memory: 12500kb

input:

3000 3000 2499825 4504
.kk.kkk.kkk.kk.....kk.kk..kk..k.kkkk....k...k........k.k........k...k.k..k..k..kk....k.kkkkk..k....kk.k.k...k............kk.kk.k..kk.kk.k.k..k.......k.k....kk.k.kk.k.kk.k..kkkk..k..kkk.kk..k.kk.k..k..kkkk...k......k...kkk..kkk...kkk..kk..kkk...kkk.k...k..kk..k..kkk.......kk......

output:

3037

result:

ok "3037"

Test #104:

score: 0
Accepted
time: 189ms
memory: 12324kb

input:

3000 3000 4224215 4737
.........k.kk............k..k.k........................k.k.k..........k...k...kk........k............kk...k...k.......................................k..k.k..........kk.......k.....k.........kkk............k.kk................kk...k.......k...k.....k..............k......kk.......

output:

6112

result:

ok "6112"

Test #105:

score: 0
Accepted
time: 172ms
memory: 12452kb

input:

3000 3000 2404391 5331
...kkk......k..kk........k.....k.kkkk.k.kk.k....kkkk.kk.k...k..k...........k...k.....k.k..kk.kk.k..k.kk...k..k...k...k.k..k.........k....k.......k..k....kkkkkkk.k.kk..kk....kkkk.......k.k.k....k..........kkk.k.k..k..k...kk..kkk..k...k..kk............k.kk.k....k....k...k...k..k...

output:

4554

result:

ok "4554"

Test #106:

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

input:

3000 3000 6403339 5433
kkkk.kkkk.kkkkk.kkkk.kkkkkk.kkkkkkkkkk.kk.kkk.kkkkkkkkkkkkkkkk.kkkkkkkkkkkk.kk.kk.kkkk.kk.kkk...kkkkkkkkkkk.k..kkkkkkk.kk.kkkk.kkk.kkk.kk.kk.kkkkkkkkkkk.kkkkk..kkkkkkkkkk..kkkkkkkkk.kk.kkkkk.kkkkk.kk.kkkkk.kkkkkkkkkkkkkkkkkkk.kkkk.kk.kkkkk.kkk.kkkkkkkk..k..kkk.k.kk.kkkk.kkk.kk...

output:

19539

result:

ok "19539"