题目描述

移动底盘在栅格地图上行走时，机器人本体有足迹半径，还要保留安全距离。请先把障碍物周围不可通行的区域膨胀出来，再判断从起点到终点是否存在四方向通路。

设输入的足迹半径和安全距离为 r_body、d_safe，栅格膨胀半径为 R = ceil(r_body + d_safe)。对每个格子，若它到最近障碍格的八方向最短步数不大于 R，则不可通行。起点或终点不可通行时直接输出不可达。

若可达，输出最短四方向步数，以及路径上所有格子的最小安全余量；在最短步数相同的情况下，保留最小安全余量更大的路径。

输入格式

第一行输入地图尺寸 H W。

第二行输入 r_body d_safe。

接下来 H 行，每行一个长度为 W 的字符串，. 表示空地，# 表示障碍。

最后一行输入 sr sc tr tc，表示起点和终点的 1-based 行列坐标。

输出格式

若不可达，输出 UNREACHABLE。

若可达，输出：

REACHABLE steps margin

其中 steps 为最短步数，margin 为整数安全余量。

判定规则

使用标准输出比较。障碍距离使用八方向 BFS 计算；实际移动只允许上下左右四方向。只有障碍距离严格大于 R 的格子可以通行。

数据范围与测试提示

• 正式测试会覆盖样例没有出现的边界输入，请不要依赖样例规模或样例顺序写特判。
• 输出只包含题目要求的字段，不要输出调试信息；浮点结果按题面要求保留 6 位小数。
• 通道宽度、足迹半径和障碍距离可能刚好卡在边界上，请严格区分可通行、贴边和碰撞。
• 若存在多个可执行通道，应按题面给出的代价和编号规则选择，不要只输出第一个看起来可行的通道。
• 网格坐标为 1-based；膨胀半径按 ceil(r_body + d_safe)，障碍距离用八方向，移动只允许四方向。

样例

输入样例 1

5 6
0.5 0.4
......
.##...
......
...#..
......
1 1 5 6

输出样例 1

UNREACHABLE

输入样例 2

3 3
1 0
#..
...
...
1 2 3 3

输出样例 2

UNREACHABLE