旅行者 1 号太空探测器(不要与无畏级星舰混淆)很久以前于 1977 年发射,目前正处于离开太阳系的边缘。随着它在太空中进一步航行,它被程序设定为在它遇到的任何恒星系统中留下无线电信号信息,以尽可能长地标记探测器的路径。
让我们假设一个恒星系统可以用一个具有 $N$ 行 and $M$ 列的矩形网格表示,将空间划分为 $N \times M$ 个相等的单元格。每个单元格可以包含一个行星、一个黑洞,或者为空。探测器从一个预先确定的空单元格向四个轴对齐的方向之一(“U”表示上,“R”表示右,“D”表示下,“L”表示左)广播信号。
广播后,信号沿同一行/列呈直线传播,直到到达一颗行星,在那里它会被偏转 90 度到另一个方向。有两种行星,我们分别用 / 和 \ 表示。偏转规则如下图所示:
当信号进入包含黑洞的单元格,或传播到矩形网格边界之外时,信号将永久离开系统。已知信号从当前单元格传播到相邻单元格需要 $1$ 秒。
编写一个程序,确定探测器需要广播信号的方向,使信号在系统内停留的时间尽可能长,输出最优方向以及相应的最长时间。如果信号可以无限期地留在系统中,则输出 “Voyager” 代替所需的时间。
输入格式
输入的第一行包含两个正整数 $N$($1 \le N \le 500$)和 $M$($1 \le M \le 500$)。
接下来的 $N$ 行中,每行包含 $M$ 个来自字符集 {"/", "\", "C", "."} 的字符,其中 / 和 \ 代表两种行星,C 代表黑洞,. 代表空单元格。
最后一行包含两个正整数 $PR$($1 \le PR \le N$)和 $PC$($1 \le PC \le M$),分别代表探测器所在单元格的行号和列号。
输出格式
输出的第一行必须包含所需的最佳广播方向(“U”、“R”、“D” 或 “L”)。如果解不唯一,请按照以下优先级顺序选择第一个最优解:首先是 “U”,然后是 “R”,接着是 “D”,最后是 “L”。
输出的第二行必须包含所需的最长时间(或信息)。
子任务
在价值至少 50% 总分的测试数据中,信号将无法无限期地留在系统中。
样例
输入格式 1
5 5 ../.\ ..... .C... ...C. \.../ 3 3
输出格式 1
U 17
输入格式 2
5 5 ....\ \..\. ./\.. \../C .\../ 1 1
输出格式 2
D 12
输入格式 3
5 7 /.....\ ../..\. \...../ /.....\ \.\.../ 3 3
输出格式 3
R Voyager
说明
第一个样例的解释(* 代表信号的路径):
起点 'U' 方向 'R' 方向 'D' 方向 'L' 方向
../.\ *.*** ../.\ ../.\ ../.\
..... *.*.* ..... ..... .....
.CS.. *C*.* .C*** .C*.. .C*..
...C. *..C* ...C. ..*C. ...C.
\.../ ***** \.../ \.*./ \.../
17 秒 3 秒 3 秒 1 秒