uva10409測資B

Input:
2
north
east
1
north
2
south
south
2
west
south
5
east
north
south
west
west
2
east
south
4
south
west
north
south
5
north
north
east
east
east
3
west
west
west
8
east
east
south
west
east
east
south
west
13
north
west
north
east
south
north
east
west
north
west
north
north
west
1000
west
west
south
south
south
south
east
south
north
west
west
west
north
east
west
east
east
east
east
west
east
east
south
south
east
south
west
north
north
south
west
west
south
east
south
east
north
west
south
east
east
east
south
north
south
east
south
south
west
south
west
north
west
west
south
south
west
south
south
south
north
west
west
south
west
north
south
north
north
south
south
west
west
south
north
west
south
west
north
west
east
west
south
south
south
east
east
west
north
east
west
west
west
west
west
east
north
east
north
east
south
west
north
east
south
north
north
north
north
south
east
east
south
west
west
north
west
west
east
south
south
south
north
east
east
east
east
south
south
west
west
north
west
south
north
west
north
north
west
east
west
south
east
north
west
south
east
west
west
east
south
south
east
south
north
south
east
east
north
west
east
east
east
north
south
west
east
south
west
south
south
west
west
north
east
north
north
east
west
west
north
west
west
west
north
south
north
east
south
east
south
east
east
north
north
west
east
south
east
east
north
east
south
south
north
east
east
east
east
north
west
north
west
east
south
south
south
west
south
west
west
east
west
east
north
east
east
east
east
west
west
south
south
west
west
south
west
west
east
west
north
north
north
south
south
west
west
west
south
south
north
south
west
east
east
west
east
south
west
west
east
south
east
south
east
west
north
west
west
south
north
north
east
west
south
north
south
west
south
east
south
north
north
south
south
east
south
south
north
west
north
east
north
west
east
east
east
west
north
east
south
north
north
west
north
north
west
west
south
south
east
east
south
north
south
south
west
east
west
north
west
west
south
east
west
north
north
west
north
north
north
north
west
east
south
east
west
south
south
west
west
west
west
east
north
south
north
west
west
east
north
south
west
west
west
west
north
south
north
west
north
west
west
west
east
west
west
east
west
north
north
south
east
north
north
south
east
east
east
east
north
east
west
east
north
east
south
east
east
east
west
north
north
west
south
north
west
south
east
east
north
east
east
west
west
south
north
south
west
west
north
north
west
west
south
east
north
north
north
west
east
north
west
east
north
west
west
east
east
east
south
west
east
north
north
south
south
east
west
west
south
west
west
west
south
west
east
east
south
north
west
north
east
west
north
north
north
north
east
west
east
west
west
south
north
north
north
east
north
north
east
north
east
east
south
north
north
west
west
east
north
east
east
north
north
east
south
west
east
west
west
south
west
south
north
east
east
north
north
north
south
west
south
north
south
north
south
east
south
south
south
west
south
south
east
west
west
south
east
west
south
south
west
south
north
east
west
south
east
west
east
east
west
west
west
west
east
east
west
west
south
south
north
north
east
south
east
east
north
south
north
east
north
south
east
south
north
south
north
west
west
east
south
north
north
north
south
north
north
east
south
west
north
north
east
west
east
south
south
east
east
east
east
south
west
west
south
west
east
north
west
east
south
east
west
east
west
south
west
north
south
east
south
west
south
north
west
east
north
north
east
south
east
east
north
south
north
north
north
north
south
west
south
east
east
west
east
west
south
east
south
west
west
south
west
west
west
east
west
north
north
south
north
south
north
south
north
west
south
east
south
south
west
north
north
west
west
north
east
west
south
east
east
south
west
east
north
east
north
west
west
north
south
west
south
north
south
south
south
south
west
east
east
east
south
east
east
south
east
south
south
south
west
south
west
west
west
east
north
south
west
south
west
north
north
south
north
south
east
east
south
south
east
north
west
west
west
south
west
east
south
south
east
east
east
north
north
north
west
east
north
west
west
north
west
east
north
east
east
south
south
east
east
east
north
west
west
south
east
east
south
south
west
east
south
west
south
west
north
east
south
north
west
south
south
east
west
south
west
north
north
east
north
south
east
west
north
south
east
north
west
south
north
west
north
south
south
south
east
west
west
north
north
west
south
east
west
west
east
east
west
south
south
east
north
south
south
east
north
north
west
north
north
east
north
east
east
west
south
south
east
north
east
west
east
south
south
west
west
south
east
south
east
north
west
west
south
west
west
south
north
south
south
south
north
south
north
east
south
south
east
south
east
east
west
west
west
south
west
west
south
north
north
south
west
west
south
north
west
west
south
north
east
west
west
south
north
east
north
east
north
north
south
west
east
south
west
east
north
west
south
west
east
east
south
west
east
east
east
east
north
east
west
south
west
south
north
east
west
north
north
west
north
south
west
west
south
north
south
south
west
north
north
west
east
west
east
south
west
east
south
west
east
east
south
east
south
north
north
north
west
west
north
north
east
west
east
south
east
west
west
south
east
east
south
east
west
north
north
north
west
south
west
west
west
north
west
east
east
south
north
west
south
north
south
west
east
south
west
west
south
south
west
east
north
east
east
north
north
east
west
east
north
east
west
west
west
north
south
north
0
Output:
3
5
6
2
4
2
4
4
3
2
4
1