Description

给一个 n 行 m 列的迷宫，每个格子要么是障碍物要么是空地。每个空地里都有一个权值。你的 任务是从找一条(r1，c1)到(r2，c2)的路径，使得经过的空地的权值之和最小。每一步可以往上下 左右四个方向之一移动一格，但不能斜着移动，也不能移动到迷宫外面或者进入障碍物格子。

如下图，灰色格子代表障碍物。路径 A->B->D->F->E 的权值为 10+3+6+14+8=41，它是从 A 到 E 的最优路径。 注意，如果同一个格子被经过两次，则权值也要加两次 。

为了让题目更有趣(顺便增加一下难度)，你还需要回答另外一个问题:如果你每次 必须转弯 (左转、右转或者后退，只要不是沿着上次的方向继续走即可)，最小权值是多少?比如，在 上图中，如果你刚刚从 A 走到 B，那么下一步你可以走到 D 或者 A，但不能走到 G。在上图 中，A 到 E 的最优路径是 A->B->D->H->D->F->E，权和为 10+3+6+2+6+14+8=49。注意，D 经 过了两次。

Input

输入包含不超过 10 组数据。每组数据第一行包含 6 个整数 n, m, r1, c1, r2, c2(2 ≤ n, m ≤ 500, 1 ≤ r1, r2 ≤ n, 1 ≤ c1, c2 ≤ m). 接下来的 n 行每行包含 m 个格子的描述。每个格子要么是一个 1~100 的整数,要么是星号“*”(表示障碍物)。起点和终点保证不是障碍物。

Output

对于每组数据,输出两个整数。第一个整数是“正常问题”的答案,第二个整数是“有趣问 题”的答案。如果每个问题的答案是“无解”,对应的答案应输出-1。

4 4 1 2 3 2
7 10 3 9
* 45 6 2
* 8 14 *
21 1 * *
2 4 1 1 1 4
1 2 3 4
9 * * 9
2 4 1 1 1 4
1 * 3 4
9 9 * 9

Case 1: 41 49
Case 2: 10 -1
Case 3: -1 -1