### 问题描述 小蓝有一天误入了一个混境之地。 好消息是：他误打误撞拿到了一张地图，并从中获取到以下信息： 1. 混境之地是一个 $n \cdot m$ 大小的矩阵，其中 `#` 表示墙，无法通行， `.` 表示普通的道路， `k` 表示散落在地图中的钥匙。 2. 他现在所在位置的坐标为 $(A, B)$ ，而这个混境之地出口的坐标为 $(C, D)$ ，当站在出口时且携带最少一把钥匙即表示可以逃离混境之地。 3. 地图中可能存在不止一把钥匙。 坏消息是： 1. 地图中可能没有钥匙。 小蓝可以往上下左右四个方向行走，每走一步耗时一分钟。 小蓝想知道他能否逃离这个混境之地，如果可以逃离这里，输出最少需要消耗多少时间 ，反之输出 `-1` 。 ### 输入格式 第一行输入两个正整数 $n, m$ ，表示矩阵的大小。 第二行输入四个正整数 $A, B, C, D$ ，表示小蓝当前所在位置的坐标，以及混境之地出口的坐标。 接下来输入 $n$ 行，每行 $m$ 个字符，表示混境之地的地图，其中 `#` 表示墙，无法通行， `.` 表示普通的道路， `k` 表示散落在地图中的钥匙。 ### 输出格式 输出数据共一行一个字符串： - 若小蓝可以逃离混境之地，则输出最少需要消耗多少时间 。 - 若小蓝无法逃离混境之地，则输出 `-1` 。 ### 样例输入1 ```txt 5 5 1 1 5 5 ....# #.#.. k.#.. .#... ...#. ``` ### 样例输出1 ```txt 12 ``` ### 样例解释1  从 $(1, 1)$ 到 $(5, 5)$ 的最短道路为： 1. $(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 1)$ 拿到钥匙。 2. $(3, 1) \rightarrow (4, 1) \rightarrow (5, 1) \rightarrow (5, 2) \rightarrow (5, 3) \rightarrow (4, 3) \rightarrow (4, 4) \rightarrow (4, 5) \rightarrow (5, 5)$ 到达终点。 ### 样例输入2 ```txt 5 5 1 1 5 5 ....# #.##. k.#.. ##... ...#. ``` ### 样例输出2 ```txt -1 ``` ### 样例解释2  可以证明不存在一条路径可以从起点到达终点。 ### 数据范围 对于所有测试样例， $1 \leq n, m \leq 1000$ 。 数据保证起点和终点一定为普通道路。