QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#77456#5514. MazeCrysfly100 ✓1510ms448992kbC++112.5kb2023-02-14 19:02:512023-02-14 19:02:54

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-14 19:02:54]
  • 评测
  • 测评结果:100
  • 用时:1510ms
  • 内存:448992kb
  • [2023-02-14 19:02:51]
  • 提交

answer

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
using namespace std;
inline int read()
{
	char c=getchar();int x=0;bool f=0;
	for(;!isdigit(c);c=getchar())f^=!(c^45);
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
	if(f)x=-x;return x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 6000005
#define inf 0x3f3f3f3f

int n,m,k;
string mp[maxn];


int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

int P(int o,int x,int y){
	return o*n*m+x*m+y;
}
int dis[maxn*5];
bool vis[maxn*5];

int q[maxn*10];
int hd=maxn*5,tl=maxn*5-1;

int ddx[5][2]={{0,0},{1,0},{1,0},{-1,0},{-1,0}};
int ddy[5][2]={{0,0},{0,1},{0,-1},{0,-1},{0,1}}; 

pii B(int x,int y){
	return mkp(x/k,y/k);
}

int L(int x){
	return x*k;
}
int R(int x){
	return (x+1)*k-1;
}

void go(int x,int d){
	if(dis[x]>d){
		dis[x]=d;
		q[--hd]=x;
	}
}

inline void go(int o,int x,int y,int d){
	x=max(x,0),y=max(y,0);
	x=min(x,n-1),y=min(y,m-1);
	int u=P(o,x,y);
	if(dis[u]>d){
		dis[u]=d;
		q[++tl]=u;
	}
}

void work()
{
	ios::sync_with_stdio(0),cin.tie(0); 
	cin>>n>>m>>k;
	memset(dis,63,sizeof dis);
	int sx,sy,tx,ty;
	cin>>sx>>sy>>tx>>ty;
	For(i,0,n-1)cin>>mp[i];
	--sx,--sy,--tx,--ty;
	q[++tl]=P(0,sx,sy); dis[P(0,sx,sy)]=0; 
	while(hd<=tl){
		int U=q[hd++];
		int o=(U/(n*m)),x=((U%(n*m))/m),y=(U%m);
		int d=dis[U];
		if(vis[U])continue;
		vis[U]=1;
	//	cout<<o<<" "<<x<<" "<<y<<" "<<d<<"\n";
		if(o==0){
			For(i,0,4){
				int xx=x+dx[i],yy=y+dy[i];
				if(xx>=0 && yy>=0 && xx<n && yy<m && mp[xx][yy]!='#')
					go(P(0,xx,yy),d);
			}
			int bx=x/k,by=y/k;
			int rbx=R(bx),rby=R(by);
			
			go(3,rbx,rby,d+1);
			
			go(2,x-k,rby,d+1);
			go(4,rbx,y-k,d+1);
			go(3,rbx,y+k,d+1);
			go(3,x+k,rby,d+1);
			
			go(1,x-k+1,y-k,d+1);
			go(1,x-k+1,y-k+1,d+1);
			go(2,x-k,y+k-1,d+1);
			go(2,x-k+1,y+k,d+1);
			go(3,x+k-1,y+k,d+1);
			go(3,x+k,y+k-1,d+1);
			go(4,x+k,y-k+1,d+1);
			go(4,x+k-1,y-k,d+1);
			
		}else{
			For(i,0,1){
				int xx=x+ddx[o][i],yy=y+ddy[o][i];
				if(xx>=0 && yy>=0 && xx<n && yy<m && (xx/k)==(x/k) && (yy/k)==(y/k))
					go(P(o,xx,yy),d);
			}
			go(P(0,x,y),d);
		}
	}
	cout<<dis[P(0,tx,ty)];
}

signed main()
{
	work();
	return 0;
}
/*

6 6 1
1 6
6 1
..#.#.
##.###
####.#
...###
##.##.
.#.###


6 7 2
6 4
3 1
..#.#.#
##.##..
.######
#..#.#.
.######
..#.##.
*/ 

詳細信息

Subtask #1:

score: 8
Accepted

Test #1:

score: 8
Accepted
time: 28ms
memory: 311860kb

input:

31 32 1
25 22
5 3
################################
################################
.###############################
.###############################
##..###############.############
###.###############.############
#####.##########################
###.#.##########################
###.##############...

output:

26

result:

ok single line: '26'

Test #2:

score: 0
Accepted
time: 35ms
memory: 311024kb

input:

31 32 1
31 5
18 30
................................
..........................#.....
................................
.................#..............
................................
................................
....#...........................
................................
....................

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 28ms
memory: 310308kb

input:

31 32 1
7 10
1 32
.#...#.####...#.####..###..####.
.#.##.#..#.###.#.#####.#..#..##.
.#.#######.########..#.#....#.#.
####.##########.####.#..###...##
####.##....####.####..####.##.##
##.###..#####..#.###..#.##.#.#.#
####.###...##.........###.#.####
.##..##.##.######....##.#####.##
####.#.###.##.#......

output:

5

result:

ok single line: '5'

Test #4:

score: 0
Accepted
time: 32ms
memory: 311892kb

input:

31 32 1
18 18
1 18
#################.##############
################################
################################
################################
################################
################################
###############.################
################################
#################...

output:

15

result:

ok single line: '15'

Test #5:

score: 0
Accepted
time: 32ms
memory: 310792kb

input:

1 1000 1
1 597
1 432
..........................................................#..........................................................................................................................................#................................................................#...................

output:

0

result:

ok single line: '0'

Test #6:

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

input:

1 1000 1
1 354
1 826
#############################################################.#########################################################################################################################################################################################################################...

output:

463

result:

ok single line: '463'

Test #7:

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

input:

1 4 1
1 4
1 3
#...

output:

0

result:

ok single line: '0'

Test #8:

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

input:

1 45 1
1 8
1 20
#######.####.#####..#####################.###

output:

9

result:

ok single line: '9'

Test #9:

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

input:

3 13 1
1 5
2 3
.....##.....#
.#....##.##..
......#......

output:

0

result:

ok single line: '0'

Test #10:

score: 0
Accepted
time: 28ms
memory: 311116kb

input:

1 2 1
1 1
1 2
..

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 37ms
memory: 310268kb

input:

1 148 1
1 91
1 89
.####.#.###...#..####..####.###..#...#.##.#####.######.#.#....#...####..##.#.#.##...##...#.##.#.#####.#####...#.#.###.#.#...##...###..#...##..##.###

output:

1

result:

ok single line: '1'

Test #12:

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

input:

2 84 1
1 11
1 62
.#..#.##.#.#.##.#.##.#.#...######.#.###...##.#####....##.##.#..###.###.##...##.#...#
.#....##.#.#..#...#....##..###..#.##.#...###.#.#.###...##.#....#...##.#..####.#.###.

output:

20

result:

ok single line: '20'

Test #13:

score: 0
Accepted
time: 34ms
memory: 310252kb

input:

1 59 1
1 6
1 20
#.###.########.###..##.####.###.##.##########.########..#.#

output:

11

result:

ok single line: '11'

Test #14:

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

input:

31 32 1
31 5
18 30
................................
..#...####.######..##.#.####.##.
..#.#.####.#####.##..######..#..
.##.####.#.#.#...##.##########..
..#...###.#####...####.#####.##.
.#..###....#.#.#.##..###.#..#.#.
.#.###..###.###.#####.#.#######.
..#...#.####.########...#..####.
..#..#.##...........

output:

0

result:

ok single line: '0'

Test #15:

score: 0
Accepted
time: 37ms
memory: 310216kb

input:

31 32 1
17 32
11 7
................................
.#.##.#..#.###.#######.#.###.##.
.#.#######.#########.#.#....#.#.
.###.##########.####.#..###.#.#.
.######.#..##########.####.##.#.
.#.###..######.#.###..#.##.#.#..
.###.###.#.##........######.###.
.##.###.##.######....##.#####.#.
.#####.###.####.....

output:

2

result:

ok single line: '2'

Test #16:

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

input:

31 32 1
7 11
13 25
................................
.##############################.
.##############################.
.##############################.
.##############################.
.##############################.
.#########.####.###############.
.##############################.
.################...

output:

11

result:

ok single line: '11'

Test #17:

score: 0
Accepted
time: 32ms
memory: 310568kb

input:

244 245 1
226 133
105 7
.####.##################################################.###.#############.########.#######.#########################################.################.####.#################.######################################.###########.######.#####.######.
.####.######.#####.#####.#####...

output:

163

result:

ok single line: '163'

Test #18:

score: 0
Accepted
time: 32ms
memory: 310652kb

input:

1 46212 1
1 39597
1 10273
#########################################.########################.##############################################################################################.##################.########.####################.##########################################.####################...

output:

28589

result:

ok single line: '28589'

Test #19:

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

input:

244 245 1
226 133
105 7
..................................................#...............................................................................................#........................................................#.........................................
.................................

output:

0

result:

ok single line: '0'

Test #20:

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

input:

244 245 1
214 117
83 245
.##..#.###.##.#.###.#..#####....#..##.##..##.##.#.###.#.##.####.###.....#.#...###.#.###..##.#.##.####..##..#..##....#.###.##.#########.#.#.##.##.#.####.##.##.##.#.##.##..##.##.#..#.#...##..##..#..#..#..####.#.###.##.#..#.#####....##.##.##.#.##..
#.###.##.#..###...###########...

output:

45

result:

ok single line: '45'

Test #21:

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

input:

244 245 1
15 226
207 34
########################################################################################################################################################################.############################################################################
##############################...

output:

340

result:

ok single line: '340'

Test #22:

score: 0
Accepted
time: 34ms
memory: 313464kb

input:

1 60000 1
1 59085
1 9263
.........................................................................................................................................................................................................................................................#............................

output:

496

result:

ok single line: '496'

Test #23:

score: 0
Accepted
time: 58ms
memory: 312792kb

input:

1 60000 1
1 57861
1 18234
##################.###########.##################.###################################################################.#################.#####.##########################################################################.###########################.#########.##################....

output:

39210

result:

ok single line: '39210'

Test #24:

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

input:

244 245 1
226 133
105 7
.....................................................................................................................................................................................................................................................
..#...#.#..####..####.......##...

output:

2

result:

ok single line: '2'

Test #25:

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

input:

244 245 1
214 117
83 245
.....................................................................................................................................................................................................................................................
..###.##.#..###...###########...

output:

8

result:

ok single line: '8'

Test #26:

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

input:

244 245 1
15 226
207 34
.....................................................................................................................................................................................................................................................
.#############################...

output:

44

result:

ok single line: '44'

Test #27:

score: 0
Accepted
time: 53ms
memory: 314232kb

input:

387 387 1
335 36
90 357
##########.##########.#######.#########.####.##########################.#################.##############################################################.######################.###################.##.###########.#####################.############.##################.#.#########...

output:

384

result:

ok single line: '384'

Test #28:

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

input:

2 30695 1
1 15156
1 6032
#..####.##..##..##.##.##..######.##.#.###.###########...####.#.###.#.###.#..###.#.###....###.#####..#...##.##.######.####.#######.######..#...#.#.##....##.##.#..#.#######.#.####.#.#####.##......###.#.#...#..#####.#.###.#####.############..###.#.#####.#...#.##...#..#.###..##....

output:

4487

result:

ok single line: '4487'

Test #29:

score: 0
Accepted
time: 68ms
memory: 313088kb

input:

387 387 1
55 282
267 35
.......................................................................................................................................................................................................................................................................................

output:

0

result:

ok single line: '0'

Test #30:

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

input:

387 387 1
287 270
56 102
#.#####.###..#..#.##..######...####..####.###..####.....#######.##..##..#.###.#..#..##.##.#...#.#.#.#.####.##...#.##..#.#.#..####.##.##.###......#.####..#####.####..##.#.#.#####..####.####.###.###..#.....#######.###.###.##..#.##..#...###..############.#.###.#..##.##..####.##...

output:

66

result:

ok single line: '66'

Test #31:

score: 0
Accepted
time: 58ms
memory: 313724kb

input:

387 387 1
182 105
119 379
##########################.######################################################################################################################################################################################################.################################################...

output:

312

result:

ok single line: '312'

Test #32:

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

input:

1 150000 1
1 113832
1 2038
.............................................................................#......................................................................................................................................................................................................

output:

1092

result:

ok single line: '1092'

Test #33:

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

input:

1 150000 1
1 6957
1 130571
####.##########################################################################.################################################################################.################################################.###############################################################...

output:

122389

result:

ok single line: '122389'

Test #34:

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

input:

387 387 1
55 282
267 35
.......................................................................................................................................................................................................................................................................................

output:

11

result:

ok single line: '11'

Test #35:

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

input:

387 387 1
287 270
56 102
......................................................................................................................................................................................................................................................................................

output:

35

result:

ok single line: '35'

Test #36:

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

input:

387 387 1
369 107
192 382
.....................................................................................................................................................................................................................................................................................

output:

21

result:

ok single line: '21'

Test #37:

score: 0
Accepted
time: 320ms
memory: 342744kb

input:

1224 1225 1
106 825
1167 186
##################################.#######.##..##.#.####.############.######.################.###################.#########.###########################.#####.####################.###############################.#######################.#######.########################.###...

output:

1112

result:

ok single line: '1112'

Test #38:

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

input:

16 10623 1
16 1171
14 2438
###.#....#.##..#.#.#.#.##.#.#..#.###..###.#..#...##..#.###..#...##.####.#......##...#..#..###...#..#####.#..##.#.###.#...#.##..#####.#######.....#.....#######.##.#....#.#...###..##..####.####.#.###.#####.#.##.###...#.....##.###.#.#.......#.###.##.#.###########.##.......##....

output:

185

result:

ok single line: '185'

Test #39:

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

input:

1 184339 1
1 58622
1 95339
.....#.....#.##.#.....#................#.....#.....#.#........#......................##.......#..#.....#....#.....##......#.................#............##.#....#..##......#...#.............#.......##.#............#.#....#....#...#...#..##.#...................#..#....##..#...

output:

5653

result:

ok single line: '5653'

Test #40:

score: 0
Accepted
time: 83ms
memory: 316404kb

input:

185 1158 1
170 697
18 48
#########.########.###.####.##########.################.#.##.#######.##.##.########.#.#############.####..###.##.####.###..###.####.#################.##..#######.#.###..#.#####..#.#.##.#.####.#.###########.####.###################..#####.############.###.#####.###..######..#...

output:

453

result:

ok single line: '453'

Test #41:

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

input:

2 121141 1
1 84070
2 47224
########.#.######.#.#####.##.###.##.####.#...####..#...#.#####.##.###.#.#######.##.##.######.###.#####.#####.####...#..#####.###########.####...#.########..##..####.###.###.####.###.#.###..####..###.##.####.##.#######.#..######.#.#....###.##.##.###.####...#.#.#.##.##.###.#...

output:

23385

result:

ok single line: '23385'

Test #42:

score: 0
Accepted
time: 197ms
memory: 325672kb

input:

6 123737 1
3 116020
4 86192
...#..#..#.............#.#.##.##...#..#...#...#...........#..#...#......##......#.#...#..#.##..#####..........#.#.....#.#.####......#....#.....##.##.####...........#.#.##..###.....#.#.#...#.#..#..#.#.#..#..#....#..#.......#...#...#...#.#.##..#..#..##......#..#...#...#.......

output:

1725

result:

ok single line: '1725'

Test #43:

score: 0
Accepted
time: 193ms
memory: 327172kb

input:

5 160357 1
1 41933
1 68874
##########.###.##.#.#####..#.#####.###..##.#############################.#############.##.#####.##########.##########.###.############..########.#####.#.######.###..####.####.##########.#####.###.##########..#.#######.##.###.#..#.###############.##############.###.###..###...

output:

20843

result:

ok single line: '20843'

Test #44:

score: 0
Accepted
time: 383ms
memory: 346020kb

input:

1224 1225 1
520 1165
390 755
.............................#....................................................................................................................................................................................................................................................

output:

0

result:

ok single line: '0'

Test #45:

score: 0
Accepted
time: 380ms
memory: 344272kb

input:

1224 1225 1
1155 1123
435 159
###....#.#.##.##.####.##.###.##########.##.####.#.#..##.##..#..####...#..#.....#####....####.###.#####...#..#..#....###.#....#....#.##.#.....##...##.#...##...####.####..#.#####.##..#.##.##.#.###.#..##.##.##..###.##..#.....#############.#####.#.##...##.#.####.#########.#...

output:

276

result:

ok single line: '276'

Test #46:

score: 0
Accepted
time: 319ms
memory: 342972kb

input:

1224 1225 1
533 1130
900 376
############################################################.###############################.########################.######################################################################.###############################################################.##################...

output:

1015

result:

ok single line: '1015'

Test #47:

score: 0
Accepted
time: 212ms
memory: 342736kb

input:

1 1500000 1
1 32769
1 947728
.................................................................................................................................................#................................................................................................................................

output:

9041

result:

ok single line: '9041'

Test #48:

score: 0
Accepted
time: 212ms
memory: 343176kb

input:

1 1500000 1
1 1314999
1 652665
##########################################################################################.###################################################.#############################################################################################.################################...

output:

655757

result:

ok single line: '655757'

Test #49:

score: 0
Accepted
time: 387ms
memory: 343800kb

input:

1224 1225 1
969 785
150 464
...................................................................................................................................................................................................................................................................................

output:

37

result:

ok single line: '37'

Test #50:

score: 0
Accepted
time: 374ms
memory: 343680kb

input:

1224 1225 1
1155 1123
435 159
.................................................................................................................................................................................................................................................................................

output:

49

result:

ok single line: '49'

Test #51:

score: 0
Accepted
time: 330ms
memory: 343868kb

input:

1224 1225 1
533 1130
900 376
..................................................................................................................................................................................................................................................................................

output:

407

result:

ok single line: '407'

Subtask #2:

score: 19
Accepted

Test #52:

score: 19
Accepted
time: 33ms
memory: 311544kb

input:

3 6 2
2 1
3 3
...###
..##..
#..###

output:

0

result:

ok single line: '0'

Test #53:

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

input:

4 24 4
3 4
3 3
..#...##.#...###...###.#
.##.#..##.##.##..#.####.
#.......#.#.#...#.#####.
######....######.#...#.#

output:

0

result:

ok single line: '0'

Test #54:

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

input:

2 136 2
1 133
2 45
#############################################.##################.#.#######.##############.#################.##############.##.######.###
####.########.###############.####.###..####.#.###.#################.##..##############.###.############################################

output:

41

result:

ok single line: '41'

Test #55:

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

input:

31 32 31
6 13
22 29
................................
................................
..............................##
......#.........................
................................
................................
............#...................
................................
...................

output:

0

result:

ok single line: '0'

Test #56:

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

input:

31 32 31
17 32
22 6
...##.#...#...###.##.#.##.###.##
###...#.#..#..#.#.##..##.#######
###.#.#.###.######.#.#..###..###
..#.#.##....#.#.###.########....
####.#.#.#############.###.#.###
#..###.#######.##.#.###.##.####.
#####.###..###...##.###..##...#.
.##.#.###..####...#####..#..#.##
.....####.#....#...

output:

1

result:

ok single line: '1'

Test #57:

score: 0
Accepted
time: 37ms
memory: 311456kb

input:

31 32 31
31 1
28 28
################################
##########################.#####
#.####################.#########
################################
################################
.###############################
################################
################################
################...

output:

1

result:

ok single line: '1'

Test #58:

score: 0
Accepted
time: 37ms
memory: 311804kb

input:

2 500 2
2 127
2 384
#..##..#####...##...##.#...#..#.##...###.##.###.##..##.#.####.#..##...#######.##.###.#####..#..####.#####...#....##..######.##....####..####..##.....####..#..##.#.####...#.##.##.##..######..#.##.#.##..#######..#.###.##.#.####.#.#..#.#..#...#########.###.#.##.###.##.#...##....###....

output:

76

result:

ok single line: '76'

Test #59:

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

input:

10 77 6
6 3
1 51
..###...#.#..#.##........##........#...##....#...#.#.....#........##......#..
##.........#.#....#.#.##.##......#.#..#..#.........#...#..#..##..#....#.###..
.......##...##....#......#...#..#.#####............#....#........#.#........#
..#......#...##.....#...##..#.#..##..##..#...##.....

output:

2

result:

ok single line: '2'

Test #60:

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

input:

3 86 3
2 57
1 6
####...##########.################.#.#.#.#########.###########################.##..###
#.#####.######.##.#################.##.############.####..#######.########.###########
##.#####.##.##.########.##.#####.################################.############.#######

output:

16

result:

ok single line: '16'

Test #61:

score: 0
Accepted
time: 32ms
memory: 311320kb

input:

12 50 4
10 13
3 13
#.########.####.####.#.######.######.#####.#####.#
####..########.######..#.#.##..##.##...###.##..###
#.##########.#.#########.####.####.###.#####.##.#.
.######.#####.#.###############.#.####.####..##...
###########.##.###.#####.##.########..#...##.####.
#########.#######.##..####...

output:

2

result:

ok single line: '2'

Test #62:

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

input:

4 52 3
2 33
3 39
....#.............#...............#....##...##....#.
#..#....................#..#.....#.##..#....#.#..#..
.#..........#.....................#...............#.
.#...#.....##......#..#......##.....................

output:

0

result:

ok single line: '0'

Test #63:

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

input:

16 49 2
1 43
7 40
##########################################.######
####.############.###############################
#################################################
#################################################
##.####.#########################################
################################...

output:

3

result:

ok single line: '3'

Subtask #3:

score: 16
Accepted

Test #64:

score: 16
Accepted
time: 33ms
memory: 311300kb

input:

35 60 20
3 60
2 44
.#....##.#.###..##.#.#....#.....#..#..#.##.#..#....###.####.
#.#......#.####..####...#...#......#........####....##.#.###
.#..#.....#.####..#.##..#.#.#...#.##..#.#..#######....#..##.
.#.#...##..#.##.......#......##......####...##.##..##.#....#
#...#.......#..#..#...#.#####.##.###....

output:

1

result:

ok single line: '1'

Test #65:

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

input:

63 602 3
10 463
3 402
#.#.#..#..######.#.##.##.#########.###.##.##..#..####.#...#########..###..####.######.###.##.#.....############.####.########.#.########.##.######.###..#####.###..##.#..#..##..##.###..##.###.#######...#.##.##.#.#.##...##...####.###.##.#.#.....#####.##.#..#.##..#...######.#####....

output:

9

result:

ok single line: '9'

Test #66:

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

input:

45 1194 5
4 632
37 206
...#..#............#..........#..##....##......#...##..#..#.............#...#...........##....#.........#.#.##..........#......#..........#.....#...........#........#.#.................#................#..........##.......................#.....#..........#........#........#......

output:

0

result:

ok single line: '0'

Test #67:

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

input:

244 245 244
28 168
222 200
...#...................................................................................................................................................................#..............................................................#..............
..............................

output:

0

result:

ok single line: '0'

Test #68:

score: 0
Accepted
time: 44ms
memory: 311904kb

input:

244 245 244
175 140
70 11
##.##....###.###..######..###.#.#####.##..#.#####.#.###.###.....#....###.#####.##..#.###.####.#..##.####...#.#####.###.##..#######.##.##...#..####.#...#####.##.###.#....##..####.###.#.#####..#.#.##.###.#..#.##.####..#.#.#...#######.######.##.#..
#..#..##.####.###.###..........

output:

1

result:

ok single line: '1'

Test #69:

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

input:

244 245 244
241 52
100 202
#######.###################################################################################################################################################################.#########################################################################
###########################...

output:

1

result:

ok single line: '1'

Test #70:

score: 0
Accepted
time: 46ms
memory: 311960kb

input:

62 967 62
41 1
29 386
####.######.####.#####...##.##..##.####..######.##...######....#.#..#...#.#.###.##.###...######..#.#.####.###.##.###.#...###..##..####.####.#.#...###..#.#..#..###.....#####.##..##.####..##......#.####.##.#...##..###.#....#..##.###.#..#####.#..#.#.#.##..#..#.#..##.##.####...#.#....

output:

6

result:

ok single line: '6'

Test #71:

score: 0
Accepted
time: 50ms
memory: 312448kb

input:

202 595 58
71 324
182 516
..#.###....#.##......#............#...#.###....................#....#....#...#.##.........#.....#....#.#.......###.#........#####..#.......###......#......#.......#...##..........#.#.....#.#.................#.#...#..#.#.......#.#.##...#.#..#......#.....#.......#.#..#..#.......

output:

0

result:

ok single line: '0'

Test #72:

score: 0
Accepted
time: 58ms
memory: 311732kb

input:

387 387 387
100 184
358 250
................#...........................................................................................................................................#......................................................................................................................

output:

0

result:

ok single line: '0'

Test #73:

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

input:

387 387 387
133 20
329 125
#..##.##..###.##.##..######..#####.#.#####..#####.####.#....##.#.#.#.#.##.##..##.###....#.#..#.#.##...###########..##..#.##..##.######.##.#.#####.###.##.#....#..##.##.##.#####..#.##.##.####..#.###.##.##.#.#....###...#.#.###.##..####..##.##.#.#.#.#.###....#.###.#.#..#.###.#...

output:

1

result:

ok single line: '1'

Test #74:

score: 0
Accepted
time: 60ms
memory: 312932kb

input:

387 387 387
201 41
238 340
###########################################################################.#####################################################################################################################################################################################################...

output:

1

result:

ok single line: '1'

Test #75:

score: 0
Accepted
time: 149ms
memory: 319228kb

input:

601 723 26
258 272
578 200
#.#.....#..#.##.##.##.......#.......#...#..#.....##...##.##..###.....#.....#.#.#....###...#.#....#...##..#..#.####...#..#..#.......#..##.....###...#.#.#....#....####..###.#.##..##....##.....##.#..#.##.#.#....#......#...##.....##.......#..#.#...#..#..##...#...#....####.##.#...

output:

0

result:

ok single line: '0'

Test #76:

score: 0
Accepted
time: 303ms
memory: 323020kb

input:

103 12319 67
96 7020
42 1423
..##.###......#...#...#.........#........#....#..#...##.......#..###......###...#...##..#.##.##......##..#....#..............#.#......#.#...#...#..#..##.#..#....#.........###...#.....#..#..###...#.......#..#...##...#..####.##.#.##..##...#..#..####...#.......#.#....#..#.#...

output:

0

result:

ok single line: '0'

Test #77:

score: 0
Accepted
time: 354ms
memory: 324532kb

input:

1224 1225 1224
582 110
326 1104
..................................................................................#...........................................................................................................................................................#................................

output:

0

result:

ok single line: '0'

Test #78:

score: 0
Accepted
time: 371ms
memory: 319660kb

input:

1224 1225 1224
1024 851
437 463
##..#.###.####..##..#...#.#...##.#.#.########.#.#####..##..##.###..##..##..##.#...#.##.##.#####..###########.#.##...#.###########.####..####...#......##...###..#.#.####.#####.#.####.####.##..#.######..#.#.##.#.#.#.####....#...###.##...#..#..#####..#.#####.#...##.##......

output:

1

result:

ok single line: '1'

Test #79:

score: 0
Accepted
time: 339ms
memory: 319636kb

input:

1224 1225 1224
188 85
758 1157
#####.##.########################################################################################################################################################.###############################################################.###########################################...

output:

1

result:

ok single line: '1'

Test #80:

score: 0
Accepted
time: 374ms
memory: 320640kb

input:

72 20833 72
41 567
6 17116
##.....##.##..#..###....###.#..##..#.#...#......#.#..###.#..#.#.#..##..#.##.......#...#.###..##.#.#..#....#....##..........#..#...##...#........#..#.#.##.###.#.###....###.#....#.#...#....#.##..#.#.##.#######.#...##....#.#.......##..#..#...##.##.........#..#....#..###.##......

output:

0

result:

ok single line: '0'

Test #81:

score: 0
Accepted
time: 358ms
memory: 321028kb

input:

114 13157 114
100 43
54 9728
.....#.....##.##....##.#..###.###.#..#.#...#....#.##.....#..#.#.###................###...#..#..#.##.#...#..#.##........#...#.#..##...#..###..##.#.....#.#.....#.....##.....#.##..#.#....#..#.##..#..##..#.###.##...#.#.#.#..##...#...#...#.##.##.#.#....#..#.#.........#....##....

output:

0

result:

ok single line: '0'

Subtask #4:

score: 19
Accepted

Dependency #2:

100%
Accepted

Test #82:

score: 19
Accepted
time: 32ms
memory: 311044kb

input:

2 2234 2
1 330
1 953
#######.##############################################################################.#######################.############.#############.##################.#####################################.###########.##########################################################.#############...

output:

300

result:

ok single line: '300'

Test #83:

score: 0
Accepted
time: 51ms
memory: 313548kb

input:

2 30000 2
2 1567
2 22320
#####.##...##..#.##..###..########.##.###.##.#.##...#.#.....#...##.###..#####.#.##.#####...#####..#######.....##....####..#....#.#.....#.#..####..####....######.###.#...#..####..####.##.##.###..#..#...###.########..####.##.#####...##########.#.##..####.###.##.#...##.#..#..##...

output:

6458

result:

ok single line: '6458'

Test #84:

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

input:

15 4000 15
14 2553
11 1177
#....####.##....##.#..####.##.#####....#.######..##...###..####.#..#.######.####.##.#..####.######.##....##.#.##.......###.##.#..####....##..####.#.#####.#.###..##.#.##.############...###.##.#...##..#.#####..##..##################..#####.####.....#..##.#######.##..##.#.#.#...

output:

73

result:

ok single line: '73'

Test #85:

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

input:

24 2500 24
2 1260
23 1965
###..##.###.#..##.###..#.#..#....#...#####.#.#####...###.#....#.##.##.###.####..####..#.###..###..##.#.....#.#...#.###.##..##..#####.##.##...##.#......#######...#.#.####.#......#####.#.##.#####..##......#.#.#.#.#####.#####...###.#.#..#####..#.##...#.##.####.####.#.#.##..#.#...

output:

25

result:

ok single line: '25'

Test #86:

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

input:

39 1538 39
8 1
30 1398
#####.###.###.#...##..#....##.#######.#.###.####.......#..###..#####......#.####.###..##.#..##...#.#####.##.#..##.##########.##.#####..###...#..##.#########.###.#.##.#..#.#####.####..#.#.###.....##......#######..##..#####.#.#####..###.######...#.#.##.##...#.##....#.#.###...#.#...

output:

32

result:

ok single line: '32'

Subtask #5:

score: 5
Accepted

Dependency #4:

100%
Accepted

Test #87:

score: 5
Accepted
time: 72ms
memory: 312028kb

input:

13 10513 3
10 3868
13 183
.....##########.#...#....########.####..#.############..###..#..#.####.##########.###....#.#.##.##.#########.#...#..#########.###..###..######.#####..##..#...###.##..##.##.########.....###.##.#.####..####.#...#####.###.##..##.#.##.#.##.###..###.###.#####.##.##.###.##..#####...

output:

720

result:

ok single line: '720'

Test #88:

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

input:

2 75000 2
2 64107
2 2578
.###..##.######...######.#.#####..###...##...#########.##.###.....###...##.##.##..########..####.#.#########.#......#####..#.##.######..#.##########.##.#####.#.#..#.#.#.##..####.##.##.######.......#..######.##.##..#.#...#..#...#.#..#.#.##..#####.###.#.#.#..##.##..###..#####....

output:

19250

result:

ok single line: '19250'

Test #89:

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

input:

21 7142 21
19 909
10 6297
###..##..#.....#.####..#######.###.#.###..###.##.####.#####.#.####..###.#.##...#.....##########...#####.#...##........#.########.##.#.###.####.##.##.##.###.##.#.#...##.##..##.#...#..#.##.#..###...##.##.#####.#.###..#.#.#.#.#.###..##..#..#.#.#...#.#.##....#.#.###...###.###.....

output:

210

result:

ok single line: '210'

Test #90:

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

input:

33 4545 33
13 795
29 4232
.#.#......#.#..#..#.#.#####.#.#..##.#.###############.###.###......#..##.##..###...##.###..#####.###.##.##...##...##.###.####....#.##.#.#....#.##...#.#####..#####.####.####.##.##..##.##....##..#.####...#####.##..#..#.#...####.#######.#.#..#.##...###.#.#...#..##.#####.##.###...

output:

90

result:

ok single line: '90'

Test #91:

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

input:

53 2830 53
11 2624
46 123
.#.#.#######...###...###.###.#.##...#####..#######..#####.###..#####.##..#.######.#####.####.##..#.#.###.########......#...###.#...#..##.##.###...#.##....#.###.#.##..#####.##.####..##..#.#.##.#..#####..###.###.##.##.####.....##.###.#..##..###.#####.############.####.#####.#...

output:

43

result:

ok single line: '43'

Test #92:

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

input:

84 1785 84
48 353
12 1389
####.##....##.#.#..#.##.##.#.##.##.#####.#..###.#.#.##.#..#.#.##.#.#.#...#........##.#..######.#....#.##.######..#.###..###...#..#.##..#....#.#.##############.#.###.##.#..##.###.####.#.###.####.##.#..#.#.##..#######.######.#..##.####.#.#.#.#..##.#...#.....##.########....##....

output:

12

result:

ok single line: '12'

Subtask #6:

score: 19
Accepted

Dependency #1:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #5:

100%
Accepted

Test #93:

score: 19
Accepted
time: 94ms
memory: 314392kb

input:

13 15064 3
7 12096
2 13762
#.###.##.#.#..##..#.##.#.##...##....#.#..#.###.#.####.#.#....#..####.....###...............######.#.#####.#..#####.#.#####....###.#....###.##..###.#.#...#.....###.##.#...#####.#.......#.##..###.######.#..#.#.#..#....##.#..#.....#.#.#.####..#...#.######.#...##..##.#.#.....#...

output:

129

result:

ok single line: '129'

Test #94:

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

input:

53 6324 24
23 714
24 6040
####.####.#####..#########.######.##.#.#####.#..#..#...####.#####.###.####.####...##########..#######.###.###.#######..#####.########.##.####.######.######..######.##############.#######.#.#...#.####..#######.#...##..#######.#.##.#..#.###..#######.#.###.###############.####...

output:

195

result:

ok single line: '195'

Test #95:

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

input:

3 254000 2
1 85641
2 123859
#########.###.####..##################..######.##.###########.##....######..#####.###########.###.###.####.#.#####.##..#.###.####..#####.##.##..######.##.#########.######..#..#.##..###########.#######..#.####.####.#.###...##.###.##.##.#####.####..########.##.#.##.###.####...

output:

13367

result:

ok single line: '13367'

Test #96:

score: 0
Accepted
time: 261ms
memory: 323200kb

input:

22 45590 10
13 26636
19 11699
#.######.##.########.###.##.##.###.####..###..#.####.#..###.######.######...#####.#.####.##########.#####.#####..#.#.####.#.#######.####..#.###.#.#####.###########.####.########.##.###..############################.##..########.#.####.#.###.####.#.###.######..###.####.#...

output:

1212

result:

ok single line: '1212'

Test #97:

score: 0
Accepted
time: 347ms
memory: 331016kb

input:

37 35344 13
35 16837
35 17654
..##.#.#..##..##..###.##...#.#.#...###..#.#.#####..###########.#.###.#..#.#.#.#.##.###.##...####.#...###.....##.##.###.........####.#..###.###..#...#.###.##.#.#...#.####..#....##.##.##...####.##..##.##..##...#.#.#.####.##.#.#.##.#.#.##..#...#...##.###.#...#...##....#..#...

output:

40

result:

ok single line: '40'

Test #98:

score: 0
Accepted
time: 352ms
memory: 321588kb

input:

45 33333 45
22 1605
29 16084
.##.#.....#.###.#.#.#...#..####..##...###.#...#.##.###.##.##.#..########.#.#####.###.#.####..###...###.#.###.###.###..##....###.##.####..#######..##.###..##..#.#.##.#########.#.##.#.##......#..#.##.##.##...#..##.####.##..####..#..#.####...#######..##..##..####.###..##.#....

output:

283

result:

ok single line: '283'

Test #99:

score: 0
Accepted
time: 356ms
memory: 319264kb

input:

72 20833 72
67 6155
26 19037
.######...##...#.#.######.#.#..##..#.######.#..##..##..##.###.#######.#.#.######..#########.#######..##.######..#.##.#.#.###.......##..#..#..###.##.#.##..##.#...#..#..##...########.#######.##..###..#.########.#######.##..##.##.#...#.###.#.##.#..#.#####..#####..##..#.##.....

output:

163

result:

ok single line: '163'

Test #100:

score: 0
Accepted
time: 342ms
memory: 320800kb

input:

114 13157 114
2 8260
28 869
.###..####.#..##..##..##..#...#..#.##.####.#.##..##.#.#..####..##.#...###..###...##.##...##..###....######..##.#######..#..####.###.####.#...#.#######.##..#..#.##...######...#####.#.###.#..#####.#..######.#.#..#..#.#####..#.#..#####..####..##.##.####.######.#####.####..##...

output:

61

result:

ok single line: '61'

Test #101:

score: 0
Accepted
time: 348ms
memory: 320684kb

input:

181 8287 181
137 5084
21 272
..#####...####.#.##.#.####.##...#.######....#...#.#.#..#.##.#.##.#.#.###.#.##..#.####.#...##....##..#......#....##..####.#########......###.##.###########..#..#.#####.###.###....####.#.###...###.#......#..####.#.#########..#.#.######.#.####..##...####.#######..##.#...#.#...

output:

26

result:

ok single line: '26'

Test #102:

score: 0
Accepted
time: 351ms
memory: 319436kb

input:

45 33333 45
29 8688
9 28980
.#...#..#....#..#....#.#.#.......#.##...........#.....#.....#......####....#...#.###....#.#.#..#..#.#....#...##.#...#.#...#...#....#...##....##.......#........#......##..#.#..#...#...###.###.....#..#.....#.#...#..###.##...#.#.#.#..#..#..#......#...#.#...##.....##.#..###.#...

output:

23

result:

ok single line: '23'

Subtask #7:

score: 8
Accepted

Dependency #6:

100%
Accepted

Test #103:

score: 8
Accepted
time: 662ms
memory: 376152kb

input:

1732 1732 1
1134 183
293 1667
############################################.##############.##################.###############.#######################.########.###################.#############.#.#############.############################################################.##.############################...

output:

1564

result:

ok single line: '1564'

Test #104:

score: 0
Accepted
time: 357ms
memory: 325808kb

input:

34 48391 20
10 35471
20 29746
.##..###.####.#.##...#########..#..##.####..###.#######.##.#.######.#.######.#####.#...##.###..#.####.#####.#.#.###.########...##.####...###########.######.#.##################.##..####.##.#####.##.####.#.##.#####...####..#...##..####.##..#####..###.#.#.###..###..###.#....

output:

246

result:

ok single line: '246'

Test #105:

score: 0
Accepted
time: 494ms
memory: 348016kb

input:

191 9036 8
139 8514
84 2476
...#.#..........#...##..##....#..#......#.#..#.#.........###...#..#.....#..#..........#..#...#......#...##....##.#..#..##.#..#................#..#.#........#....#..........##.#.#....#.#......#..##.#...#..#...#.#.#......#................#.#.....#.......##............#...##...

output:

0

result:

ok single line: '0'

Test #106:

score: 0
Accepted
time: 485ms
memory: 345048kb

input:

771 2770 40
431 2092
692 1929
##############################################################################################################################.##########################################.####################################################################################################...

output:

7

result:

ok single line: '7'

Test #107:

score: 0
Accepted
time: 727ms
memory: 382208kb

input:

1732 1732 1
902 98
138 1552
.........................................................................#.........................................................................................................................................................................................................

output:

0

result:

ok single line: '0'

Test #108:

score: 0
Accepted
time: 712ms
memory: 375672kb

input:

1732 1732 1
872 409
1099 1344
#.#.###.####.##..#.###.#.#########....#####.##..####.#.#.######....#.#.#..##.##.#.#.#.######..#.##.#..##.####.....#.#.####..#..#.#.#...##.#...#....#####..##.###.#..##.###.##..##.#.#...#.#..#.#######..#.#.##..##....#..###..####.####.###.#....###.######.###....#.#.....#.....

output:

214

result:

ok single line: '214'

Test #109:

score: 0
Accepted
time: 614ms
memory: 375064kb

input:

1732 1732 1
1497 303
842 638
########################################################################################.##############################################################################################################################################################.#######################...

output:

891

result:

ok single line: '891'

Test #110:

score: 0
Accepted
time: 701ms
memory: 334532kb

input:

1732 1732 1732
456 181
1566 1525
..............................................................................................................................................................................................................................................................................

output:

0

result:

ok single line: '0'

Test #111:

score: 0
Accepted
time: 713ms
memory: 329584kb

input:

1732 1732 1732
1054 882
115 1413
#######.#..#.###.##.###.#.##.....#..#..#.##..####..#######.#..##.#..##..#.##..#......#.#..######.#.#..#..#.##.###...###############.#.##..#####.##..###.#.####.########.####..#..##########.##...#..#.##..#..#..####.##..###..#.#..####.######.#.###.##.#...#.####.########...

output:

1

result:

ok single line: '1'

Test #112:

score: 0
Accepted
time: 636ms
memory: 328932kb

input:

1732 1732 1732
1384 1517
1391 163
##################################################################################################################################.#######################################################################################################################################...

output:

1

result:

ok single line: '1'

Test #113:

score: 0
Accepted
time: 422ms
memory: 375132kb

input:

1 3000000 1
1 373836
1 2935057
.............................................................................#..................................................................................................................................................................................................

output:

25447

result:

ok single line: '25447'

Test #114:

score: 0
Accepted
time: 443ms
memory: 377112kb

input:

1 3000000 1
1 80444
1 1787839
####################################################################################################################################################################.##############################.##########################################################################...

output:

1690196

result:

ok single line: '1690196'

Test #115:

score: 0
Accepted
time: 659ms
memory: 329828kb

input:

57 52631 57
46 47146
41 2625
###.....##.##..##.#.#.#.#.###..##..###...#..#####.#.###.###..##.#..######.#.##..###.##.#####..#######...#..##..######.###.##.#.######..##.##..####.#.#.##.##.####..#########.#.######..##...#####..###...##..##.######.#.###..#####..#.#...####.####.##...##...####..#...####.....

output:

699

result:

ok single line: '699'

Test #116:

score: 0
Accepted
time: 653ms
memory: 330700kb

input:

90 33333 90
10 31119
60 18659
#.##.#######.#.#.##.##..###..#...#..#......#..####.#.#######.#.####..###.#.#.##.#.##.#..#.#.###.#.##..#...##..####.#.##.#.#.#.###....##..#..#...#..####....##..######.....#.####..####...####..#.#.#...####......#.##.##.######.#####.#.#..#...####...##.#.##..##.#.###.###......

output:

128

result:

ok single line: '128'

Test #117:

score: 0
Accepted
time: 675ms
memory: 329460kb

input:

144 20833 144
26 3250
75 9451
####.#.#..#.#.#.#.######.#..####....#..##.#####....##.#...##....##..#.#..##.#.###..####..##.#....#...#.#.#####.#.#.###..#.####..##..##.#...#####.....#.#.##...#..########.###...#######..#..#.#.##.#.#.#..######.#.##..#....#..#..#....###...###.#.###..#.###.....##..#.#.####...

output:

41

result:

ok single line: '41'

Test #118:

score: 0
Accepted
time: 654ms
memory: 331308kb

input:

228 13157 228
167 12504
80 525
##.##..#.##..##.....#.###########..#######..##..###..#.....##.###.#.######.#.###.#######..##..#.#..##....#.....#######..#####..#.#.#...#.##....###.#.###########..#.####..#.###.###########...###.###..#####.#..##.###.####.##.####.#####..##...##.#..#..####.##.#....####......

output:

51

result:

ok single line: '51'

Test #119:

score: 0
Accepted
time: 790ms
memory: 375076kb

input:

1732 1732 1
902 98
138 1552
...................................................................................................................................................................................................................................................................................

output:

24

result:

ok single line: '24'

Test #120:

score: 0
Accepted
time: 799ms
memory: 373960kb

input:

1732 1732 1
1140 1484
1239 196
................................................................................................................................................................................................................................................................................

output:

104

result:

ok single line: '104'

Test #121:

score: 0
Accepted
time: 643ms
memory: 375160kb

input:

1732 1732 1
320 975
1066 1240
.................................................................................................................................................................................................................................................................................

output:

794

result:

ok single line: '794'

Subtask #8:

score: 6
Accepted

Dependency #7:

100%
Accepted

Test #122:

score: 6
Accepted
time: 1330ms
memory: 437856kb

input:

2449 2449 1
221 573
1987 2242
###########.##.################.##.############.##############.##################.##########.##########.#########.#########.######.############################.###.########.####.##########.#########.##############.#.#######.#############.########.#######################...

output:

2243

result:

ok single line: '2243'

Test #123:

score: 0
Accepted
time: 636ms
memory: 332212kb

input:

423 7339 400
202 2322
164 6231
############.###.################.######.#.#############################.#########.####.###################.############.############.##########################################.########################.##.###################.##################.#########################...

output:

10

result:

ok single line: '10'

Test #124:

score: 0
Accepted
time: 1115ms
memory: 385272kb

input:

562 6516 8
549 2863
319 196
#.###...##.#.#...#...#.#...##.##.####.#.#.####.###.#.#.#..###..####.#....#...#.#.#.####..#...##....#....##.....#.#..###.####.......#.#...#.##..#..#.#.##..#..###..#..###......#...##.##..####.....##...####...#########..####.##.###...#.###..#.#...##...#.######..##....##..##....

output:

135

result:

ok single line: '135'

Test #125:

score: 0
Accepted
time: 1267ms
memory: 437712kb

input:

33 180735 1
30 144349
3 160285
.##..#.#.#..#.##..###.###.##########.####.########.##..####.####.####..###################.######.####..####.######.##.###.###.########.##.###.####.#.#.#####.###########.#.#####..#.###.###.############.#.###....##..###.###.########.#..#.####.####.##.#######..####.#.#.#...

output:

9056

result:

ok single line: '9056'

Test #126:

score: 0
Accepted
time: 1390ms
memory: 448992kb

input:

2449 2449 1
2367 2132
373 1253
#..................................................................#...............................................................................................................................................................................#............................

output:

0

result:

ok single line: '0'

Test #127:

score: 0
Accepted
time: 1449ms
memory: 437676kb

input:

2449 2449 1
1319 1761
2366 1093
#.###..####.#.##.#.#######.#.##.##...#.##.###...###.###.#....###.....#.#.#.####.####.####.##.##.##.#.###.######..###.#.#..#####.#..######.#.#.#.#.###..#..#.#...######..#.###..##..####..#######.##...#..#######....###.#...##..######.##.###...#.###.#####.#.#.###..#....#....

output:

284

result:

ok single line: '284'

Test #128:

score: 0
Accepted
time: 1292ms
memory: 437612kb

input:

2449 2449 1
474 22
2171 1860
#############.###############################.#########################.#######################################################################################################################################################################################################...

output:

3156

result:

ok single line: '3156'

Test #129:

score: 0
Accepted
time: 1320ms
memory: 355752kb

input:

2449 2449 2449
103 250
969 1546
................................#...................................................................................................................................................................................................................................#..........

output:

0

result:

ok single line: '0'

Test #130:

score: 0
Accepted
time: 1420ms
memory: 345564kb

input:

2449 2449 2449
2333 1437
1154 109
#.#.##.#....####..###.##.##.#.##.#....###..##.#..##.#.##.#######.###..#.#.#.#.#.####...##..#.##########....#.######.#.##.#..#####.##.#.....#.####...#..###.##...#..#.##.....##.##....#####.##...##.##.#.#..#.##.#######..########.###.#...#..#..#####.#..######..######..#...

output:

1

result:

ok single line: '1'

Test #131:

score: 0
Accepted
time: 1343ms
memory: 345528kb

input:

2449 2449 2449
1201 1533
2370 35
#############################################################################################################.###################################################################.#########################################################################################...

output:

1

result:

ok single line: '1'

Test #132:

score: 0
Accepted
time: 803ms
memory: 437500kb

input:

1 6000000 1
1 2195469
1 368116
................................................................................................................................................................................................................................................#...............................

output:

18302

result:

ok single line: '18302'

Test #133:

score: 0
Accepted
time: 801ms
memory: 437164kb

input:

1 6000000 1
1 2514105
1 5002744
.################################################################################################.#####################################.#############################.########.###########################################.###############.#################################...

output:

2463413

result:

ok single line: '2463413'

Test #134:

score: 0
Accepted
time: 1321ms
memory: 345360kb

input:

72 83333 72
56 23691
13 70663
#####.....#.##...#########.##.####..###.#.#####.....#####...#.#..####.#####.#..###.#....##.######.#.###..##.#.#######.##.##.##.#..##..##..#######.######...##.#.#.####.####.###.######.#.#.#...###..#..#.#.#..#####.#..#.#.#.##..#.#.#....#.....##..#.##.###..##...#.#####.......

output:

592

result:

ok single line: '592'

Test #135:

score: 0
Accepted
time: 1316ms
memory: 347580kb

input:

114 52631 114
27 7458
105 40769
.###.#.#..#######.#...####.#####..#.#####..#####.##.#..#..#.#.#..#.#.#######..#####..#.#...#.###.#..##.########.####.##.##.#.....#.###.#####.#...##..##..##.###......#.#.##.##.#######..#.##.##.##.....###...#.#.#.#####.###..#.#####.###...##.###...#..#.#..#######.##.#.#....

output:

273

result:

ok single line: '273'

Test #136:

score: 0
Accepted
time: 1297ms
memory: 345840kb

input:

181 33149 181
120 7874
65 28546
.###..#.######.###.##.###.#.#####.###.....#####.##.#.#.#######.#.#..#######..#...#####..####..##..##..#.###.#.####....########.#########.#.##.#######.###.#.###..#..##...#####...###.##.#...#####.#.#####.#.###..#..#.#.####.#.##...#.###.###.#####..###.####.#.#.###.####.....

output:

109

result:

ok single line: '109'

Test #137:

score: 0
Accepted
time: 1300ms
memory: 346216kb

input:

288 20833 288
248 12159
178 19038
.#####.#######.##.####...##..##.#....##.#.##.##.####..######..#..#.#.#####..#####.#..#...########.#..##########.##.##.#.####.#..#.####.###.##..##.##..##.#.##.##..######....###.#.####..#.##.####.#..######.#.#...#.#...####..###.#....#.#....#.#...##..######.....#.#.#.#...

output:

24

result:

ok single line: '24'

Test #138:

score: 0
Accepted
time: 1319ms
memory: 347348kb

input:

57 105263 57
3 7864
32 66457
....#...#...#..#.#..#...##..###...#.....##..#.#...#.#.#.#..........##....#..#.....##....#.#..#.....###....#...#.##...##...#....##..##.....#..##.#.#.#...#..#.#.##.......###.#.###..###.....#.....#........#...#..........#.#..#...####.#.#.....###..#..#...#.##..#.#..#...........

output:

6

result:

ok single line: '6'

Test #139:

score: 0
Accepted
time: 1318ms
memory: 347616kb

input:

72 83333 72
8 22180
36 50149
....#....#..##....###......##..#.....##...#.#....##...#.####..####.##..###.#.###.......######......#....###..##.##.#..###.###...#...#..#....#.###.....#.##..#.##........##.....#####......#..##.......#.##.#....#.........#..........#.....#.##.#....#.#....###.....#.###.#.#.....

output:

0

result:

ok single line: '0'

Test #140:

score: 0
Accepted
time: 1312ms
memory: 345576kb

input:

114 52631 114
48 45448
25 5761
..#...#.#......#....#...#..#.###...#..#.#...#####.##..#.#..#....#...##.#....##.....#..###...#.#.#.##..#....#..##.###.##.#.#.....#...#...###.#......##.###.#.#.###...#.#..#.#..#..............###.....##....#...#..#......#..#.#..##.#..#..##.....###.#.#.#.....#..##..###.......

output:

0

result:

ok single line: '0'

Test #141:

score: 0
Accepted
time: 1349ms
memory: 347808kb

input:

181 33149 181
71 14607
15 1097
#......##..##..##.###.#..#.#..#..#...#...##.#...###...#.#.....#.....##....#.###.#..####.#.########.####.....##.###......#.....#.#...#.#...###..#.###.....#......#.#...####...#.......#....#........#..#..##.#.....#.......#...###.#...##.#.....##.##.#.......#.##.##...#...#....

output:

1

result:

ok single line: '1'

Test #142:

score: 0
Accepted
time: 1510ms
memory: 437236kb

input:

2449 2449 1
2367 2132
373 1253
................................................................................................................................................................................................................................................................................

output:

43

result:

ok single line: '43'

Test #143:

score: 0
Accepted
time: 1474ms
memory: 437732kb

input:

2449 2449 1
1366 1852
2224 451
................................................................................................................................................................................................................................................................................

output:

179

result:

ok single line: '179'

Test #144:

score: 0
Accepted
time: 1241ms
memory: 438160kb

input:

2449 2449 1
474 22
2171 1860
..................................................................................................................................................................................................................................................................................

output:

291

result:

ok single line: '291'

Extra Test:

score: 0
Extra Test Passed