蔡蔡和芳芳发现了一个奇怪的房间。
这个房间可以看成由 $1\times 1$ 的方块构成的 $n$ 行 $m$ 列矩阵,某些位置上摆放着一个正偏 $45^\circ$ 或反偏 $45^\circ$ 的平面镜。同时,从房间的某处水平或竖直射入一束激光,激光在房间内穿行、反射,最终可能从房间的边缘离开,或是在房间内无限循环。
具体来说:
现在已知光线从第 $x$ 行第 $y$ 列正中以方向 $d$ (含义见输入数据)射入,还有房间内镜子的摆放情况,蔡蔡和芳芳想考考聪明的你,光线要走多远才会离开房间?
第一行为5个整数 $n,m,x,y,d\ (1\le n,m\le500,1\le x \le n, 1 \le y \le m)$ 分别代表房间的长,宽,以及光线射入位置的行号,列号和方向 ,$d$ 为 $0,1,2,3$ 分别代表向上、向右,向下,向左。
接下来$n$行,每行一个长度为$m$的字符串,其中:
保证光线射入位置是空地。
如果光线能离开房间,输出一行一个整数,代表光线走过的路程。
否则,输出Forever!
。
光线依次经过的格子为(5,1),(4,1),(3,1),(3,2),(3,3),(3,4),(3,5),(2,5),(1,5),(1,4),(1,3),(2,3),(3,3),(4,3),(5,3),共15格。