GO命令有一个整数参数n∈{1, 2, 3}，接到该命令后机器人向它面向的方向前进n米。

　　TURN命令有一个参数，该参数或者为left，或者为right。接到该命令后它会按照参数所指定的方向左转或右转90度。

　　每个命令的执行耗时1秒。

　　请你帮研究员们写一个程序，要求该程序能够计算出机器人从一个地方移动到另一个地方所需的最小时间。

　　输入

　　输入文件包含很多段，每一段是很多行。除了最后一段外，每一段都定义了一个场地以及机器人的初始位置和方向。每一段的第一行是用单个空格分开的两个整数M≤50和N≤50，接下来有M行，每行有N个用单个空格分开的0或1，分别表示空地和障碍物（轨道在空地之间）。每段的最后一行是四个正整数B1, B2, E1, E2，每个整数后面有一个空格，接着用一个单词表示机器人初始的方向。B1, B2表示机器人的初始位置相对西北角的坐标，E1, E2表示机器人的目标位置相对西北角的坐标，对机器人到达目标位置时的方向不作要求。我们用（行，列）型的坐标，也就是说左上角（西北角）的坐标为0, 0，右下角（东南角）的坐标为M, N。方向用north, west, south和east四个单词之一给出。

　　最后一段只包含数字M = 0和N = 0。

　　输出

　　输出文件中的每一行都和输入文件中的一个段相对应，用一个整数给出机器人从初始位置面朝初始方向经过若干命令移动到目标位置所需的最小时间，如果机器人不可能移动到目标位置则输出-1。输入文件中最后的空段不需要在输出文件中有内容相对应。

　　例
　
　　输入文件：
　　9 10
　　0 0 0 0 0 0 1 0 0 0
　　0 0 0 0 0 0 0 0 1 0
　　0 0 0 1 0 0 0 0 0 0
　　0 0 1 0 0 0 0 0 0 0
　　0 0 0 0 0 0 1 0 0 0
　　0 0 0 0 0 1 0 0 0 0
　　0 0 0 1 1 0 0 0 0 0
　　0 0 0 0 0 0 0 0 0 0
　　1 0 0 0 0 0 0 0 1 0
　　7 2 2 7 south
　　0 0

　　输出文件：
　　12