D. Building Gondola (gondola)
time limit per test
7 seconds
memory limit per test
2048 MB
input
standard input
output
standard output
Examples
Input
4 5 1 2
X?..
X.X?
?X??
XX?.
?X?X
1 1 4
2 1 4
Output
1
1
Input
3 5 1 2
.?.
.?X
X?X
X?X
X?X
1 1 2
1 2 3
Output
2
4
Input
4 2 1 2
X.X.
X.X.
2 1 4
0 2 3
Output
2
0
Input
6 6 2 7
?.?..?
??.X.?
?X?X.?
?X??XX
.X???X
??XX??
0 4 6
3 1 6
2 2 5
0 4 5
1 3 5
1 5 6
2 1 4
Output
0
12
4
0
4
3
9