题目背景

CTSC1998 D2T1

题目描述

罗杰游戏由一张棋盘和罗杰构成。棋盘由很多个小格组成，每个小格上刻有一个数字。其为 $-1$ 或 $0$ 至 $255$ 之间的一个数。罗杰是一个立方体，有六个面，每个面上分别有一个 $1$ 至 $6$ 之间的数字。

我们开始时把罗杰放在棋盘中的一个小格上，然后让其向前、后、左、右四个方向翻滚至邻近小格中。

游戏要求经过若干次翻滚后，让罗杰到达指定小格。

罗杰不得进入标有 $-1$ 的小格，否则游戏结束。

罗杰每进入一个小格后，将其顶面的数字同该小格的数字相乘，所得结果累加即得到罗杰的旅行费用。

开始时我们能看到罗杰的某些面上的数字，也可以指定当罗杰最终到达目的格时某些面上应出现的数字。对于不确定的数字，我们可以在合法的基础上任意指定。

任务一

罗杰只能向前或向右翻滚。

任务二

罗杰可以自由活动。

输入格式

输入文件的第一行是数字 $1$ 或 $2$ 。表示是任务一还是任务二。

文件的第二行是两个整数 $M$ 和 $N$ ，给出了棋盘的列数和行数。

接下来的 $N$ 行每行表示棋盘的一行，有 $M$ 个数，依次给出了该行上每列的数。

其后的两行分别给出了罗杰的出发点信息和到达点信息。

每行开始的两个正整数给出了该格子的列号和行号。

接下来的六个数字分别表示了罗杰的顶，底，前、后、左、右各面的数字。 $0$ 表示可以任意指定。

输出格式

输出文件的第一行给出罗杰的最小旅行费用。

如果罗杰不可能按要求到达目的地，则输出 $-1$ 。

否则其后每行给出罗杰的旅行情况：

从出发格到目的格，每行表示了罗杰的一个位置，

依次给出罗杰的当前旅行费用、所在格的列编号、行编号，以及罗杰6个面上的数字。

注意这时你的程序必须给出罗杰的完整信息，即各面上的数字不能为 $0$。

2 
10 10
1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1
1 1 1 9 8 7 6 5 4 1
1 1 9 8 7 6 5 4 1 1
1 1 8 7 6 5 4 1 1 1
1 1 7 6 5 4 1 1 1 1
1 1 6 5 4 1 1 1 1 1
1 1 5 4 1 1 1 1 1 1
1 1 4 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
3 3 0 0 0 0 0 0
8 8 0 0 0 0 0 0

44
0 3 3 6 5 3 1 2 4
3 3 2 3 1 5 6 2 4
5 4 2 2 4 5 6 1 3
6 5 2 1 3 5 6 4 2
10 6 2 4 2 5 6 3 1
13 7 2 3 1 5 6 2 4
15 8 2 2 4 5 6 1 3
16 9 2 1 3 5 6 4 2
20 10 2 4 2 5 6 3 1
26 10 3 6 5 4 2 3 1
28 10 4 2 4 6 5 3 1
29 9 4 1 3 6 5 2 4
34 9 5 5 6 1 3 2 4
38 8 5 4 2 1 3 5 6
41 8 6 3 1 4 2 5 6
43 8 7 2 4 3 1 5 6
44 8 8 1 3 2 4 5 6

提示

【数据范围】

$M \le 40$ , $N \le 40$ 。