uva10409測資A

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