Sample Input 1

6 7
 _ _ _ _ _ _ _ 
| |  _ _|  _  |
| | |_ _| |_| |
| |_ _ _|  _ _|
| |  _ _| |   |
| | |_ _| |   |
|_|_ _ _|_|_ _|
6 3 7 2 2 2

Sample Output 1

1

Sample Input 2

2 3
 _ _ _ 
|     |
|_ _ _|
-1 -1

Sample Output 2

3

Sample Input 3

3 3
 _ _ _ 
|  _  |
| | | |
|_|_|_|
-1 1 1

Sample Output 3

1

Sample Input 1

4 3
0110
0 2 3
1 3 4
F 2 3

Sample Output 1

1 1
2 1
3 4

Sample Input 1

1
1
0

Sample Output 1

1
1

Sample Input 2

3
2 0 1
3 5 4

Sample Output 2

11
3 2 5 3 4 5 3 4 5 1 4

Sample Input 1

5 4
1 2
2 3
3 4
4 5

Sample Output 1

13

Sample Input 1

4
0 0
1 0
1 1
0 1

Sample Output 1

0.25
0.25
0.25
0.25

Sample Input 2

4
0 0
10 0
9 1
1 1

Sample Output 2

0.46944215849887844
0
0.5305578415011215
0

Sample Input 1

4 2 2 1 1

Sample Output 1

2.82842712

Sample Input 1

6 10 120 110
90 100 110 120 130 140

Sample Output 1

GOAL

Sample Input 2

8 10 0 10
10 4 -2 -8 -1 5 10 15

Sample Output 2

NO GOAL

Sample Input 3

1 1 2 3
1

Sample Output 3

GOAL

Sample Input 1

2 1

Sample Output 1

1

Sample Input 2

5 3

Sample Output 2

2
3
4
4
3
2
1
0
0
0

Sample Input 1

IICCPPCC
INTERNATIONALCOLLIGIATEPROGRAMMINGCONTEST
GOODLUCKHAVEFUN
ENJOYYOURTIMEATHCMUTEANDHAPPYCODDING
WISHYOUMANYACCEPTEDCODE
RIGIONALICPCRIGIONALICPCRIGIONALICPC
$

Sample Output 1

5
2
0
2
2
10

Sample Input 1

4 2
10 20 30 40
1 2
2 3
3 4

Sample Output 1

70

Sample Input 2

4 1
10 20 30 40
1 2
1 3
1 4

Sample Output 2

30

Sample Input 3

4 2
10 20 30 40
1 2
1 3
1 4

Sample Output 3

-1

Sample Input 1

2
aabbccdd
2
aaa
2

Sample Output 1

ababcdcd
OH NO!

Sample Input 1

2
3 5 6 9
6 9 12 22

Sample Output 1

5
19